AtCoder Regular Contest 078
分类:
IT文章
•
2022-08-26 12:46:37
我好菜啊，ARC注定出不了F系列。要是出了说不定就橙了。
题意：把序列分成左右两部分，使得两边和之差最小。
![]()
#include<cstdio>
#include<algorithm>
#define MN 2100001
using namespace std;
int n,m,a[MN];
long long sum1=0,sum2=0,mmh=1e18;
long long _abs(long long x){return x<0?-x:x;}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum2+=a[i];
for (int i=1;i<n;i++) if (sum1+=a[i],_abs(sum2-sum1-sum1)<mmh) mmh=abs(sum2-sum1-sum1);
printf("%d
",mmh);
}
View Code
题意：一棵树，初始有一个白点一个黑点，两人轮流操作，分别把白区域的黑区域拓展一个点，问谁先无法操作。
![]()
#include<cstdio>
#include<vector>
#include<algorithm>
#define MN 2100001
using namespace std;
int n,m,a[MN],x,y,fa[MN],s[MN],d[MN];
vector<int> v[MN];
void dfs(int x,int f){
fa[x]=f;s[x]=1;
for (int i=0;i<v[x].size();i++)
if (v[x][i]!=f){
d[v[x][i]]=d[x]+1;
dfs(v[x][i],x);
s[x]+=s[v[x][i]];
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);v[y].push_back(x);
}
dfs(1,0);
x=n;y=d[x]-(d[x]-1>>1);
while (d[x]!=y) x=fa[x];
if (n-s[x]>s[x]) puts("Fennec");else puts("Snuke");
}
View Code
题意：猜数，每次可以询问一个数，回答这个数的大小和字典序与答案的大小关系是否相同。
逐位确定即可。
![]()
#include<cstdio>
#include<vector>
#include<algorithm>
#define MN 2100001
using namespace std;
int n,m,a[MN],x,y;
vector<int> v[MN];
long long g=0;
bool bo=1;
char s[100]="999999999999",c[10];
int main(){
for (int i=0;i<=10;i++){
int l=i==0,r=9,mid;
while (l<r){
mid=l+r>>1;
s[i]=mid+'0';
printf("? %s
",s);
fflush(stdout);
scanf("%s",c);
if (c[0]=='Y') r=mid;else l=mid+1;
}
if (l!=9) bo=0;
g=g*10+l;
printf("? %d
",g+1);
fflush(stdout);
scanf("%s",c);
if (bo){
if (c[0]=='N') return printf("! %d
",g),fflush(stdout),0;
}else{
if (c[0]=='Y') return printf("! %d
",g),fflush(stdout),0;
}
s[i]=l+'0';
}
}
View Code
![]()
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,map[16][16],x,y,z,mmh[1<<15][15],o[1<<15][15];
inline int work(int a,int b){
int mmh=0;
for (int i=0;i<n;i++)
if ((a>>i)&1) mmh+=o[b][i];
return mmh;
}
int main(){
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
memset(mmh,63,sizeof(mmh));
while(m--){
scanf("%d%d%d",&x,&y,&z);x--;y--;
map[x][y]=map[y][x]=z;
}
for (int i=0;i<(1<<n);i++)
for (int j=0;j<n;j++){
o[i][j]=0;
for (int k=0;k<n;k++)
if ((i>>k)&1) o[i][j]+=map[j][k];
}
mmh[1][0]=0;
for (int i=0;i<(1<<n);i++)
for (int j=0;j<n;j++)
if ((i>>j)&1){
for (int k=0;k<n;k++)
if (map[j][k])
if (!((i>>k)&1)) mmh[i|(1<<k)][k]=min(mmh[i|(1<<k)][k],mmh[i][j]+work(i,1<<k)-map[j][k]);
int u=(1<<n)-1-i;
for (int p=u;p;p=(p-1)&u) mmh[i|p][j]=min(mmh[i|p][j],mmh[i][j]+work(i^(1<<j),p));
}
printf("%d
",mmh[(1<<n)-1][n-1]);
}
