https://codeforces.com/contest/1594
A
We can obviously construct one [ − n + 1 , n ] [-n+1,n] Interval and satisfaction conditions of [− n+1,n]
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
cout << -n + 1 << ' ' << n << '\n';
}
return 0;
}
B
This is the original question of NOIP
https://ac.nowcoder.com/acm/problem/16668
- The question is for you to find n 0 , n 1 , n 2 . . . n^0,n^1,n^2... n0,n1,n2 k k Who's k? We can push it. The first one is obviously n 0 n^0 n0, the second smallest is n 1 n^1 n1, the third is n 0 + n 1 n^0+n^1 n0+n1, the fourth smallest is n 2 n^2 n2, and so on. If you are very sensitive to binary, you can find that each number is a binary number, and the binary numbers come exactly in order, that is, the first small is ( 1 ) 2 (1)_2 (1) 2. The second is ( 10 ) 2 (10)_2 (10) 2. The third is ( 11 ) 2 (11)_2 (11) 2, then the second k k k is small k k The binary number corresponding to k, so we enumerate k k Each bit of the binary number corresponding to k can be accumulated
- I really didn't see this layer when I first did this problem a long time ago, but now it's very simple to see this problem
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll fastpow(ll base, ll power){
ll ans = 1;
while(power){
if(power & 1) ans = ans * base % MOD;
base = base * base % MOD;
power >>= 1;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
long long n, k;
cin >> t;
while(t--){
cin >> n >> k;
ll ans = 0;
ll m = 0;
while(k){
if(k & 1){
ans = (ans + fastpow(n, m)) % MOD;
}
m += 1;
k >>= 1;
}
cout << ans << '\n';
}
return 0;
}
C
Our purpose is to make all characters in this string become target characters. The operation method is as follows: select a number x ∈ [ 1 , n ] x\in[1,n] x ∈ [1,n], for each position of the string, if the position subscript cannot be x x x. Integer division, then replace this position with the target character. Now ask the minimum operand
- Obviously, if we choose n n n. So except n n All positions other than n will become the target character, and then we can choose n − 1 n-1 n − 1 is enough, so the maximum number of operations is 2 2 2； Operand is 0 0 0 is obvious; So the key to the problem now is that the operand is 1 1 What should I do when
- If a number is not a factor of the subscript of any non target character, the number of operations is 1. In other words, if all subscripts that a factor can achieve are target characters, the number of operations is 1, x x x is this factor, and we can use one O ( n n ) O(n\sqrt n) O(nn ) to solve this problem
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t, m;
string s;
char c;
cin >> t;
while(t--){
cin >> m >> c;
cin >> s;
int nm = 0;
for(int i=0;i<m;i++){
if(s[i] != c) nm += 1;
}
if(nm == 0){
cout << 0 << '\n';
continue;
}
bool found = false;
for(int d=1;d<=m;d++){
int cc = d;
for(int i=d;i<=m;i+=d){
if(s[i - 1] != c){
cc = -1;
break;
}
}
if(cc != -1){
found = true;
cout << 1 << '\n';
cout << cc << '\n';
break;
}
}
if(!found){
cout << 2 << '\n';
cout << m - 1 << ' ' << m << '\n';
}
}
return 0;
}
D
imposter: liar
crewmate: Crew
Several sets of relations are given, expressed as u u u said v v v is a liar or a crew member. Now ask how many liars there are through these relationships. If there is a contradictory relationship, then output − 1 -1 −1
- The answer to this question is i d e a idea idea we might be able to find out if u u u said v v v is a liar, then u u u and v v v must belong to different sets; If u u u said v v v is the crew, they must belong to the same set, so we can divide these people into several groups, which is the idea of joint search set
- The groups we divided above are just a few divisions, and there is no bias, so let's first u u u node is a liar or crew, in D f s Dfs Observe whether there are contradictions during Dfs, that is, according to u u u derived v v The group in which v is located is inconsistent with the group in which it is now located
- If there is no contradiction, take the larger number and add it to the answer, because the two situations are complementary
- From the perspective of program implementation, we can make the program simple by using the property of XOR, that is, if two people are in the same group, the set weight is 0 0 0, otherwise 1 1 1，
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t, n, m, u, v;
string s;
cin >> t;
while(t--){
cin >> n >> m;
vector<vector<pair<int, int> > > g(n);
for(int i=0;i<m;i++){
cin >> u >> v >> s;
u -= 1;
v -= 1;
if(s[0] == 'i'){
g[u].push_back(make_pair(v, 1));
g[v].push_back(make_pair(u, 1));
}else{
g[u].push_back(make_pair(v, 0));
g[v].push_back(make_pair(u, 0));
}
}
vector<int> used(n);
vector<int> now(n);
vector<int> cnt(2);
bool flag = true;
int ans = 0;
function<void(int)> Dfs = [&](int u){
used[u] = 1;
cnt[now[u]] += 1;
for(auto i : g[u]){
int v = i.first;
if(!used[v]){
now[v] = (now[u] ^ i.second);
Dfs(v);
}else{
if(now[v] != (now[u] ^ i.second)){
flag = false;
}
}
}
};
for(int i=0;i<n;i++){
if(!used[i]){
cnt[0] = cnt[1] = 0;
now[i] = 0;
Dfs(i);
ans += max(cnt[0], cnt[1]);
}
}
cout << (flag ? ans : -1) << '\n';
}
return 0;
}
E1
Ask the possible coloring scheme of this binary tree
- According to the knowledge of simple permutation and combination, it is obvious that there are six schemes for the root node and four schemes for all the remaining nodes. If the number of layers of the binary tree is k k k. So the answer is 6 × 4 2 k − 2 6\times4^{2^k-2} 6×42k−2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll fastpow(ll base, ll power){
ll ans = 1;
while(power){
if(power & 1) ans = ans * base % MOD;
base = base * base % MOD;
power >>= 1;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll k;
cin >> k;
cout << 6ll * fastpow(4, pow(2, k) - 2) % MOD;
return 0;
}
E2
pass first
F
yes s s s animals and n n n fences, now say, if you can put these animals in these fences, and there is no empty fence, and there is at least one continuous section k k k animals, so this farm is l u c k y lucky lucky farm; At the same time, any distribution without empty fences can make the farm a l u c k y lucky lucky farm, then this farm is a i d e a l ideal ideal farm
- Now give the farm s , n , k s,n,k s. N, K, ask if this farm is l u c k y lucky lucky farm
- Construction problem, first, if s < n s<n S < n obviously, it is illegal for us to construct at will; If s = n s=n s=n, then arbitrary construction is legal; If s > n s>n s> N, consider a worst-case illegal structure as follows 1 , 1 , 1 , 1... ⏟ k − 1 individual 1 , k + 1 , 1 , 1 , 1 , 1 , . . . ⏟ k − 1 individual 1 , k + 1 , 1 , 1... \underbrace{1,1,1,1...}_{k-1 1},k+1,\underbrace{1,1,1,1,...}_{k-1 1},k+1,1,1 k − 1 1,1,1,1..., k+1,k − 1 1 1,1,1,1,...,k+1,1,1...
- We first put an animal in each fence, which requires n n n animals, the rest s − n s-n s − n animals, then k k The position of the multiple of k needs to be placed more k k k, the number of animals needed is ⌊ s k ⌋ × k \lfloor\frac{s}{k}\rfloor\times k ⌊ks⌋ × k. So the necessary condition for constructing this illegal situation is s − n ≥ ⌊ s k ⌋ × k s-n\geq \lfloor\frac{s}{k}\rfloor\times k s−n≥⌊ks⌋ × k. NO is output at this time
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
long long s, n, k;
cin >> s >> n >> k;
if(s == k) cout << "YES\n";
else if(s < k) cout << "NO\n";
else if(s - n < n / k * k) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}