A
暴力就完事了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=1007;
ll a[N][N];
ll Ans[N];
int main(){
int n=input();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=input();
if(n==2){
printf("%lld %lld
",a[1][2]/2,a[1][2]-a[1][2]/2);
exit(0);
}
for(int i=2;i<=n-1;i++){
Ans[i]=(a[i-1][i]+a[i][i+1]-a[i-1][i+1])/2;
}
Ans[1]=a[1][2]-Ans[2];
Ans[n]=a[n-1][n]-Ans[n-1];
for(int i=1;i<=n;i++){
printf("%lld ",Ans[i]);
}
}
E
每次对答案产生贡献只有最右下角的棋子才会对答案产生贡献（类似博弈论的推理），那么只要统计当前位置被翻转了多少次，边维护前缀和边算答案就行了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=507;
int n,m;
char s[507];
int a[N][N];
int d[N][N];
int main(){
int T=input();
while(T--){
n=input(),m=input();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++){
a[i][j]=s[j]=='0'? 0:1;
}
}
for(int i=1;i<=n+5;i++)
for(int j=1;j<=m+5;j++)
d[i][j]=0;
int cnt=0;
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
d[i][j]+=d[i+1][j]+d[i][j+1]-d[i+1][j+1];
if((d[i][j]+a[i][j])%2==1)
d[i][j]++,cnt++;
}
}
if(cnt%2) printf("call
");
else printf("aoligei
");
}
}
G
答案显然是:到所有标记点的距离*2-到最远的点的距离。树dp维护这个式子，就可以做出来了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define PII pair<int,ll>
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
const int N=5e5+7;
ll dis1[N],dis2[N],sum[N],siz[N];
vector<PII> G[N];
int n,k;
void Ins(int u,int v,ll w){
G[u].pb(mp(v,w));
G[v].pb(mp(u,w));
}
void modify(int dis,int u){
if(dis>dis1[u]) dis2[u]=dis1[u],dis1[u]=dis;
else if(dis>dis2[u]) dis2[u]=dis;
}
void dfs1(int u,int fa){
for(auto vv:G[u]){
ll v=vv.fr,w=vv.sc;
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]){
sum[u]+=2*w+sum[v];
modify(dis1[v]+w,u);
}
}
}
void dfs2(int u,int fa){
for(auto vv:G[u]){
ll v=vv.fr,w=vv.sc;
if(v==fa) continue;
sum[v]=sum[u]-2*w*(siz[v]==k)+2*w*(siz[v]==0);
if(dis1[u]==dis1[v]+w){
if(siz[u]-siz[v]!=0){
modify(dis2[u]+w,v);
}
}else modify(dis1[u]+w,v);
dfs2(v,u);
}
}
int main(){
n=input(),k=input();
for(int i=1;i<n;i++){
int u=input(),v=input(),w=input();
Ins(u,v,w);
}
for(int i=1;i<=k;i++){
int x=input();
siz[x]=1;
}
dfs1(1,0),dfs2(1,0);
for(int i=1;i<=n;i++){
printf("%lld
",sum[i]-dis1[i]);
}
}
C
转换为染色问题，相当于求给图中每一个点染色，有边相连的点颜色不能相同，最少需要多少种颜色，而最多的路径便是颜色的数量-1。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=20;
int G[N][N],color[N];
int Ans=0x3f3f3f3f;
int cnt=0;
int n,m;
bool check(int u,int c){
for(int i=1;i<=n;i++){
if(G[u][i]&&color[i]==c){
return 0;
}
}
return 1;
}
void dfs(int dep){
if(cnt>=Ans) return;
if(dep>n){Ans=min(cnt,Ans);return;}
for(int i=1;i<=cnt+1;i++){
if(check(dep,i)){
color[dep]=i;
if(i>cnt){
cnt++;
dfs(dep+1);
cnt--;
}else dfs(dep+1);
color[dep]=0;
}
}
}
int main(){
n=input(),m=input();
for(int i=1;i<=m;i++){
int u=input(),v=input();
G[u][v]=G[v][u]=1;
}
dfs(1);
printf("%d
",Ans-1);
}