我好菜啊，ARC注定出不了F系列。要是出了说不定就橙了。
C - Splitting Pile
题意：把序列分成左右两部分，使得两边和之差最小。
#include<cstdio>
#include<algorithm>
#define MN 2100001
using namespace std; int n,m,a[MN];
long long sum1=,sum2=,mmh=1e18;
long long _abs(long long x){return x<?-x:x;}
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&a[i]),sum2+=a[i];
for (int i=;i<n;i++) if (sum1+=a[i],_abs(sum2-sum1-sum1)<mmh) mmh=abs(sum2-sum1-sum1);
printf("%d\n",mmh);
}
D - Fennec VS. Snuke
题意：一棵树，初始有一个白点一个黑点，两人轮流操作，分别把白区域的黑区域拓展一个点，问谁先无法操作。
#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]=;
for (int i=;i<v[x].size();i++)
if (v[x][i]!=f){
d[v[x][i]]=d[x]+;
dfs(v[x][i],x);
s[x]+=s[v[x][i]];
}
}
int main(){
scanf("%d",&n);
for (int i=;i<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);v[y].push_back(x);
}
dfs(,);
x=n;y=d[x]-(d[x]->>);
while (d[x]!=y) x=fa[x];
if (n-s[x]>s[x]) puts("Fennec");else puts("Snuke");
}
E - Awkward Response
题意：猜数，每次可以询问一个数，回答这个数的大小和字典序与答案的大小关系是否相同。
逐位确定即可。
#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=;
bool bo=;
char s[]="",c[];
int main(){
for (int i=;i<=;i++){
int l=i==,r=,mid;
while (l<r){
mid=l+r>>;
s[i]=mid+'';
printf("? %s\n",s);
fflush(stdout);
scanf("%s",c);
if (c[]=='Y') r=mid;else l=mid+;
}
if (l!=) bo=;
g=g*+l;
printf("? %d\n",g+);
fflush(stdout);
scanf("%s",c);
if (bo){
if (c[]=='N') return printf("! %d\n",g),fflush(stdout),;
}else{
if (c[]=='Y') return printf("! %d\n",g),fflush(stdout),;
}
s[i]=l+'';
}
}
F - Mole and Abandoned Mine
题意：给一个图，要求删掉一条边，使得1到n有且只有一条简单路径。
状压dp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m,map[][],x,y,z,mmh[<<][],o[<<][];
inline int work(int a,int b){
int mmh=;
for (int i=;i<n;i++)
if ((a>>i)&) mmh+=o[b][i];
return mmh;
}
int main(){
scanf("%d%d",&n,&m);
memset(map,,sizeof(map));
memset(mmh,,sizeof(mmh));
while(m--){
scanf("%d%d%d",&x,&y,&z);x--;y--;
map[x][y]=map[y][x]=z;
}
for (int i=;i<(<<n);i++)
for (int j=;j<n;j++){
o[i][j]=;
for (int k=;k<n;k++)
if ((i>>k)&) o[i][j]+=map[j][k];
}
mmh[][]=;
for (int i=;i<(<<n);i++)
for (int j=;j<n;j++)
if ((i>>j)&){
for (int k=;k<n;k++)
if (map[j][k])
if (!((i>>k)&)) mmh[i|(<<k)][k]=min(mmh[i|(<<k)][k],mmh[i][j]+work(i,<<k)-map[j][k]); int u=(<<n)--i;
for (int p=u;p;p=(p-)&u) mmh[i|p][j]=min(mmh[i|p][j],mmh[i][j]+work(i^(<<j),p));
}
printf("%d\n",mmh[(<<n)-][n-]);
}