因为学校的某些操作。
让最近两天的(Atcoder)都能打了，挺开心的。
想上次(ABC)看错题意，失败退场。
——————————————————————————————
(A)
直接手动判断六种排列。
A
#include<iostream>
#include<cstdio>
#define ll long long
ll a,b,c;
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
//abc acb bac bca cab cba
if((b - a) == (c - b) || (c - a) == (b - c) || (a - b) == (c - a) || (c - b) == (a - c) || (a - c) == (b - a) || (b - c) == (a - b))
puts("Yes");
else
puts("No");
}
(B)
B
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define M 20
#define N 10000
struct P{
char a[M];
int key;
}e[N];
bool operator < (P a,P b){
return a.key > b.key;
}
ll n;
int main(){
scanf("%lld",&n);
for(int i = 1;i <= n;++i)
scanf("%s%d",e[i].a + 1,&e[i].key);
std::sort(e + 1,e + n + 1);
std::cout<<e[2].a + 1<<std::endl;
}
(C)
考虑到只有四位数，所以直接枚举并判断是否合法就行。
C
#include<iostream>
#include<cstdio>
#define ll long long
char ai[20];
ll ans;
inline bool check(ll now){
ll a = now / 1000,b = now % 1000 / 100,c = now % 100 / 10,d = now % 10;
for(int i = 0;i <= 9;++i)
if(ai[i] == 'o' && a != i && b != i && c != i && d != i)
return false;
else
if(ai[i] == 'x' && (a == i || b == i || c == i || d == i))
return false;
return true;
}
int main(){
scanf("%s",ai);
for(int i = 0;i <= 9999;++i){
if(check(i))
ans ++ ;
}
std::cout<<ans<<std::endl;
}
(D)
没想到(ABC)还考(min-max)对抗搜索，考虑记录的答案是第一手比第二手高多少分就行了。（据说正解是反着(dp)）
D
#include<iostream>
#include<cstdio>
#define ll long long
#define N 2005
ll h,w;
ll p[2005][2005],f[N][N];
bool v[N][N];
ll x,y;
inline ll dfs(int turn){
if(v[x][y])return f[x][y];
ll ans = turn ? -0x7f7f7f7f : 0x7f7f7f7f;
if(x + 1 <= h){
x += 1;
if(turn)
ans = std::max(ans,dfs(0) + p[x][y]);
else
ans = std::min(ans,dfs(1) - p[x][y]);
x -= 1;
}
if(y + 1 <= w){
y += 1;
if(turn)
ans = std::max(ans,dfs(0) + p[x][y]);
else
ans = std::min(ans,dfs(1) - p[x][y]);
y -= 1;
}
// std::cout<<turn<<" "<<x<<" "<<y<<" "<<ans<<std::endl;
v[x][y] = 1;
return f[x][y] = ans;
}
int main(){
scanf("%lld%lld",&h,&w);
for(int i = 1;i <= h;++i)
for(int j = 1;j <= w;++j){
char a;
while(a != '+' && a != '-')
a = getchar();
if(a == '+')
p[i][j] = 1;
else
p[i][j] = -1;
a = 'q';
}
x = 1,y = 1;
v[h][w] = 1,f[h][w] = 0;
ll k = dfs(1);
// std::cout<<k<<std::endl;
if(k > 0)
puts("Takahashi");
if(k == 0)
puts("Draw");
if(k < 0)
puts("Aoki");
}
(E)
考虑这种树上数对统计答案问题，是可以换根做的。考虑在某个点((x))为根时，求出答案为(sum_i dis(x,i))就行了。
对于换根操作，考虑到要换到的点到根的异或距离为(k)，则他到每个点的距离都要异或(k),
考虑分位，单位算贡献就好了。
E
#include<iostream>
#include<cstdio>
#define ll long long
#define N 200005
#define mod 1000000007
ll head[N],cnt;
ll n,dis[N],c[N],a[N];
struct P{int to,next;ll wi;}e[N * 2];
inline void add(int x,int y,ll w){
e[++cnt].to = y;
e[cnt].next = head[x];
e[cnt].wi = w;
head[x] = cnt;
}
inline void dfs1(int u,int f){
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v == f)
continue;
dis[v] = dis[u] ^ e[i].wi;
dfs1(v,u);
}
}
ll ans = 0;
inline void dfs2(int u,int f){
ll k;
for(int i = 0;i < 60;++i){
if(dis[u] & (1ll << i))k = n - c[i];
else
k = c[i];
ans += (1ll << i) % mod * k % mod;
ans %= mod;
}
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v == f)
continue;
dfs2(v,u);
}
}
int main(){
scanf("%lld",&n);
for(int i = 1;i <= n - 1;++i){
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs1(1,0);
for(int i = 1;i <= n;++i)
for(int j = 0;j < 60;++j)
if(dis[i] & (1ll << j))c[j] ++ ;
dfs2(1,0);
std::cout<<ans * (500000004) % mod<<std::endl;
}