A:Ehab and another construction problem
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;int main(){
int x;
scanf("%d", &x);
for(int i = ; i <= x; ++i)
for(int j = ; j <= x; ++j){
if(i%j == && i*j > x && i/j < x){
cout << i << ' ' << j << endl;
return ;
}
}
cout << - << endl;
return ;
}
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int a[N];
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i)
scanf("%d", &a[i]);
sort(a+, a++n);
int val = , b = ;
for(int i = ; i <= m; ++i){
while(b <= n && val >= a[b])
++b;
if(b > n)
puts("");
else {
printf("%d\n", a[b]-val);
val = a[b];
}
}
return ;
}
题意：要求构造一个严格递增序列。
题解：一共最多有n+1次操作，所以我们从后往前每次构造第i个数， 把他构造成对%n之后的余数为（i-1)。 最后再对整个数列%n就好了。
代码：
Copy
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int n;
int a[N];
struct Node{
int op, l, r;
};
vector<Node> ans;
int main(){
scanf("%d", &n);
for(int i = ; i <= n; ++i)
scanf("%d", &a[i]);
int val = ;
for(int i = n; i >= ; --i){
a[i] += val;
int t = a[i]%n;
if(t == i-) continue;
t = (n+(i-) - t);
val += t;
ans.pb({, i, t});
}
ans.pb({, n, n});
printf("%d\n", ans.size());
for(auto it : ans){
printf("%d %d %d\n", it.op, it.l, it.r);
}
return ;
}
D：Ehab and another another xor problem
交互题。
题解：
我们可以通过输出 0 0 来判断 a 和 b的大小。
然后我们考虑ab的二进制。
从高位往地位枚举
将第i位^1之后， 如果 a和b的亦或后的大小没发生改变， 则说明第i位是一样01码的。
将第i位^1之后， 如果 a和b的亦或后的大小发生了变化， 那么就说明第i位的01码是不一样的，并且原来大的那个数第i位是1，记录下这一位的变化， 然后前面这一位考虑进去之后，重新询问接来下的剩下位数的ab大小。
经过上面的操作，我们就确定了不一样的位置的信息，然后在去找同意位置上的信息就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int t, val, f = ;
int ans1, ans2;
int vis[N];
int xx = , yy = ;
int gg(int x, int y){
x ^= xx; y ^= yy;
if(x > y) return ;
if(x ==y) return ;
return -;
}
int main(){
printf("? 0 0\n");
fflush(stdout);
scanf("%d", &t);
f = t;
for(int i = ; i >= && f != ; --i){
int o1 = << i;
int o2 = o1 ^ val;
printf("? %d %d\n", o1, o2);
fflush(stdout);
scanf("%d", &t);
if(f == ){
if(t == -){
val ^= o1;
ans1 ^= o1;
vis[i] = ;
printf("? %d %d\n", , val);
fflush(stdout);
scanf("%d", &f);
}
}
else if(f == -){
if(t == ){
val ^= o1;
ans2 ^= o1;
vis[i] = ;
printf("? %d %d\n", , val);
fflush(stdout);
scanf("%d", &f);
}
}
}
for(int i = ; i >= ; --i){
if(vis[i]) continue;
int o1 = << i;
int o2 = val;
printf("? %d %d\n", o1, o2);
fflush(stdout);
scanf("%d", &t);
if(t == -){
ans1 ^= o1;
ans2 ^= o1;
}
}
printf("! %d %d\n", ans1, ans2);
fflush(stdout);
return ;
}
E：Ehab and a component choosing problem
题意：在一颗树上，每个点都有权值， 你可以选择k个联通块， 使得 所有选得的点的和/k的值最大， 在保证值最大的前提下， k最大。
题解：所有选择的点/k 。 我们考虑这个东西， 肯定就是 这k个块的值都是一样的。并且我们需要保证这值是图中最大的值。
那么我们可以通过dfs找到这个值最大是多少。
然后在通过dfs去check最多有多少个这种块。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 3e5 + ;
int a[N];
vector<int> vc[N];
LL ans = _INF;
LL dfs1(int o, int u){
LL val = a[u];
for(int v : vc[u]){
if(v == o) continue;
val += max(0ll, dfs1(u,v));
}
ans = max(ans, val);
return val;
}
int k = ;
LL dfs2(int o, int u){
LL val = a[u];
for(int v : vc[u]){
if(v == o) continue;
val += max(0ll, dfs2(u,v));
}
if(val == ans) ++k, val = ;
return val;
}
int main(){
int n;
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
for(int i = ,u,v; i < n; ++i){
scanf("%d%d", &u, &v);
vc[u].pb(v); vc[v].pb(u);
}
dfs1(,);
dfs2(,);
cout << 1ll * ans * k << ' ' << k << endl;
return ;
}
F：Ehab and a weird weight formula
题意：给定一棵树，每个节点有权值，并且只有所有权值中，最小值的点只有一个。 并且除了最小值的那个点， 其他的点连向的点中，一定有一个点的 v[u] < v[i]。现在要求你重构这棵树，然后使得
1. 每个点的度数 * v[i] + 2. 对与新图的每条边的{u，v} -> log(dis(u,v)) * min（a[u], a[v]) 所有和最小。
题解：
我们需要证明一个东西，即从权值最小的那个点出发之后， 对于某条链来说，深度越大的点的权值一定大于深度小的点。
假如存在一条链： A -> B -> C -> D
A是其中最小的点。
我们假设 v[B] > v[A], v[C] < v[B]
因为需要满足题目给定的那个条件， 所以 v[D] < v[C]。
那么对于D来说也需要存在一个点的值是小于D的， 但是不存在这种点， 所以这个假设是矛盾的。
我们可以简单证得 从最小点出发， 他的值是递增的。
然后我们倍增跑一下每个点的每层祖先是什么就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 5e5 + ;
int v[N];
LL ans = ;
int anc[N][];
vector<int> vc[N];
void dfs(int o, int u){
anc[u][] = o;
for(int i = ; i < ; ++i) anc[u][i] = anc[anc[u][i-]][i-];
if(o){
LL tmp = INF;
for(int i = ; i < ; ++i){
tmp = min(tmp, 1ll*v[anc[u][i]]*(i+));
}
tmp += v[u];
ans += tmp;
}
for(int v : vc[u]){
if(v == o) continue;
dfs(u, v);
}
}
int main(){
int n;
int rt = ;
scanf("%d", &n);
for(int i = ; i <= n; ++i){
scanf("%d", &v[i]);
if(v[i] <= v[rt]) rt = i;
}
for(int i = ,u,v; i < n; ++i){
scanf("%d%d", &u, &v);
vc[u].pb(v);
vc[v].pb(u);
}
v[] = v[rt];
// cout << "bug" << endl;
dfs(, rt); printf("%lld\n", ans);
return ;
}
