CodeCraft-21 and Codeforces Round #711 (Div. 2)

这场着实有点自闭

签到

竟被这题卡了好几十分钟，实际上就每次从大往小选，尽量选大的，越简单的题反而越糊涂

#include
using namespace std;
const int N=1e5+7;
int n,w,ans,a[20],id[N*10];
int main()
{
    int T;scanf("%d",&T);
    for(int i=1;i<=19;i++)id[1<i;
    while(T--)
    {
        scanf("%d%d",&n,&w);
        memset(a,0,sizeof a);
        for(int i=1,x;i<=n;++i)scanf("%d",&x),++a[id[x]];
        for(int num=1;;num++)
        {
            int rest=w;
            for(int j=19;~j;--j)
            while(a[j]&&rest>=(1<1<a[j];
            if(rest==w){printf("%d\n",num-1);break;}
        }
    }
}

f[i][j]表示i架飞机j扇门的答案，直接按照i从小到大，i相同时j从小到大转移即可

#include
using namespace std;
const int N=1005,mod=1e9+7;
int n,k,f[N][N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=k;i++)for(int j=0;j<=n;j++)f[i][j]=0;
        for(int j=0;j<=n;j++)f[1][j]=1;
        for(int i=2;i<=k;i++)
        {
            f[i][0]=1;
            for(int j=1;j<=n;j++)f[i][j]=(f[i][j-1]+f[i-1][n-j])%mod;
        }
        printf("%d\n",f[k][n]);
    }
}

容易发现每次操作只会让数字变大，于是对于一次操作，记录个数组表示从原先可能到达的值操作多少次能到达i，然后直接暴力更新即可，复杂度O(nm)

#include
using namespace std;
const int N=1e5+7;
int n,m,f[N],g[N];
int main()
{
    scanf("%d%d",&n,&m);
    f[0]=0;for(int i=1;i<=m;i++)f[i]=-1;
    for(int i=1,t,y;i<=n;i++)
    {
        long long x;
        int tmp;
        cin>>t>>x>>y;
        if(t==1)tmp=(x-1)/100000+1;
        for(int j=0;j<=m;j++)g[j]=f[j]==-1?1e9:0;
        for(int j=0;j<=m;j++)
        if(g[j]<y)
        {
            if(t==1)
            {
                if(j+tmp<=m)
                g[j+tmp]=min(g[j+tmp],g[j]+1);
            }
            else if(j)
            {
                long long pos=(x*j-1)/100000+1;
                if(pos>m)continue;else tmp=pos;
                g[tmp]=min(g[tmp],g[j]+1);
            }
        }
        for(int j=0;j<=m;j++)if(f[j]==-1&&g[j]<=y)f[j]=i;
    }
    for(int i=1;i<=m;i++)printf("%d ",f[i]);
}

这题比A还SB可是我写挂了，真没什么意义出这题，没次数限制……直接按照k[i]-k[j]排序，询问i j（注意k[i]>=k[j]），问到个Yes直接输出

#include
using namespace std;
struct node{int x,y,d;}a[505*505];
int n,num,k[505];
bool cmp(node a,node b){return a.d>b.d;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&k[i]);
    for(int i=1;ii)
    for(int j=i+1;j<=n;++j)
    a[++num]=(node){i,j,abs(k[i]-k[j])};
    sort(a+1,a+num+1,cmp);
    char op[10];
    for(int i=1;i<=num;++i)
    {
        if(k[a[i].x]<k[a[i].y])swap(a[i].x,a[i].y);
        printf("? %d %d\n",a[i].x,a[i].y),fflush(stdout);
        scanf("%s",op);
        if(op[0]=='Y'){printf("! %d %d",a[i].x,a[i].y);return 0;}
    }
    printf("! 0 0");
}

看心情补题。