比赛总结

今天比赛爆炸，颗粒未收

比赛时不太仔细，导致我很成功的将110扔掉了。（我的第17名啊?）

铁轨

栈，直接模拟。

比赛时没有发现输出只有首字母大写，将所有的字母全部大写输出，成功爆炸。

这个问题也不是第一次犯了，但仍然继续再犯。足以说明我对这个问题不够重视，希望下次能改正

#include 
    
     using namespace std;int n,a[1001],i,len,k,f[1001];int main(){    freopen("a.in","r",stdin);    n=1;    while (n)    {        scanf("%d",&n);        if (!n)break;        a[1]=1;        while (a[1])        {            scanf("%d",&a[1]);            if (!a[1])break;            for (i=2;i<=n;i++)                scanf("%d",&a[i]);            len=0; k=1;            for (i=1;i<=n;i++)            {                f[++len]=i;                while (f[len]==a[k] && k<=n) len--,k++;            }            if (k<=n) printf("No\n");else printf("Yes\n");        }        printf("\n");    }}

独立集

比赛时没有头绪。比赛后将其解出。

大致解法

用前向星边正反存起来，再从任意一个点（1号点）出发。

f[i][0]表示第i个点不选的方案数，f[i][1]表示第i个点选的方案数

则当第i个点不选时，其儿子可选可不选，所以方案数f[i][0]=(f[son][1]+f[son][0])
当第i个点选时，其相邻的点（父亲及儿子）都不能选，所以f[i][1]=f[son][0]

答案就是如此

这题说明自己的思维还不到位，需要继续锻炼

#include 
    
     using namespace std;int n,i,x,y,len,go[500001],f[100001][2],to[500001],last[100001];void make(int x,int y){    go[++len]=y; to[len]=last[x];last[x]=len;}void dfs(int x,int dad){    int k=last[x];    f[x][0]=1;f[x][1]=1;    while (k)    {        if (go[k]!=dad)        {            dfs(go[k],x);            f[x][0]=(f[x][0]*(f[go[k]][0]+f[go[k]][1]))%10081;            f[x][1]=(f[x][1]*f[go[k]][0])%10081;        }        k=to[k];    }}int main(){    freopen("a.in","r",stdin);    scanf("%d",&n);    for (i=1;i

石子游戏

比赛时没有正解思路，想水10分。考虑不够仔细，算法错误。颗粒未收

正解是博弈论

虽然我没系统的学博弈论，但根据次题还是了解了一点点（也只有一点点）

大致解法

构建数列a[i]和b[i]，使a中任意不相邻的两项的差距大于k倍。

而b[i]z则为1~i中互不相邻的几项之和

即

构造A,B数列,使得A1∼i若干个互不相邻的数的和都可等于B1∼i的数. ——LSY

先是初始值a[1]=b[1]=1

很显然，a[i+1]=b[i]+1

而b[i+1]怎么推？

我们从sigma(a[1~i])中取最大的，设该位置为j

且满足其a[j+1]*k<a[i+1]

则b[i]=b[j]+a[i+1]

造数造完后，我们现在要进行的是判断。

当x在a中存在时，则必败

否则必胜，而答案求法很玄学

令k=x,每次减去一个在a中小于k的最大值。

当k=0时，输出最后一个减数

自我感觉特别玄学

#include 
    
     using namespace std;int n,i,x,k,len,s,j,a[10000001],b[10000001];int main(){    freopen("a.in","r",stdin);    scanf("%d",&n);    for (i=1;i<=n;i++)    {        scanf("%d%d",&x,&k);        printf("Case %d: ",i);        len=0;a[1]=1;b[1]=1;s=0;        while (a[len]
     
      =1;j--)        {            if (x>=a[j]) x-=a[j];            if (!x)            {                printf("%d\n",a[j]);                break;            }        }    }}