[Codeforces #201] Tutorial

Link:

传送门

代码量很少的一套思维题

A:

试一试发现最后状态一定是所有$min,max$间$gcd$的倍数

直接判断数量的奇偶性即可

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
int n,mx,x,gcd;

int GCD(int x,int y){return !y?x:GCD(y,x%y);}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x),mx=max(mx,x),gcd=GCD(gcd,x);
    if(!gcd) gcd=1;
    puts((mx/gcd-n)%2?"Alice":"Bob");
    return 0;
}

感觉现在自己开始瞎猜结论了……

看完样例就直接觉得最终状态应该是$[1,max]$……

猜结论一定要手造数据试一试！

B:

$LCS+KMP$

只要在$dp$状态上多记录一维当前子序列匹配到的位置就能做了

输出方案的话可以用$map$记录前驱方案各维的值，不过从前向后记忆化搜索可以不用$map$

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
struct Tri{int x,y,z;};
const int MAXN=105,INF=1<<28;
map<Tri,Tri> pre;
char a[MAXN],b[MAXN],c[MAXN],ans[MAXN];
int la,lb,lc,dp[MAXN][MAXN][MAXN],nxt[MAXN],val[MAXN],tot;
//重载要写全！ 
bool operator < (const Tri &a,const Tri &b)
{
    if(a.x==b.x&&a.y==b.y) return a.z<b.z;
    else if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}

void kmp()
{
    int k=0;nxt[1]=0;
    for(int i=2;i<=lc;i++)
    {
        while(k&&c[k+1]!=c[i]) k=nxt[k];
        if(c[k+1]==c[i]) k++;nxt[i]=k;
    }
}
int cal_nxt(int x,int y)
{
    while(y&&c[y+1]!=a[x]) y=nxt[y];
    if(c[y+1]==a[x]) y++;
    return y;
}
void modify(Tri x,Tri y,int val)
{
    if(x.x>la||x.y>lb) return;    
    int &t1=dp[x.x][x.y][x.z];
    int &t2=dp[y.x][y.y][y.z];
    if(t1<t2+val)
        t1=t2+val,pre[x]=y;
}
//可以不记录pre,从前往后记忆化搜索 
void print(Tri t)
{
    int lst=0;
    while(t.x&&t.y)
    {
        if(a[t.x]==b[t.y]) 
            ans[++tot]=a[t.x],val[tot]=dp[t.x][t.y][t.z];        
        t=pre[t];
    }
    while(tot) 
        if(val[tot]!=val[tot+1]) printf("%c",ans[tot--]);
        else tot--;
}
int main()
{
    scanf("%s%s%s",a+1,b+1,c+1);
    la=strlen(a+1);lb=strlen(b+1);lc=strlen(c+1);
    kmp();
    
    for(int i=0;i<=la;i++)
        for(int j=0;j<=lb;j++)
            for(int k=0;k<lc;k++)
            {
                modify((Tri){i+1,j,k},(Tri){i,j,k},0);
                modify((Tri){i,j+1,k},(Tri){i,j,k},0);
                if(a[i+1]!=b[j+1]) continue;
                int Nxt=cal_nxt(i+1,k);
                if(Nxt==lc) continue;
                modify((Tri){i+1,j+1,Nxt},(Tri){i,j,k},1);
            }    
    
    int res=0,t;
    for(int i=0;i<lc;i++)
        if(res<dp[la][lb][i]) res=dp[la][lb][i],t=i;
    if(!res) return puts("0"),0;
    print((Tri){la,lb,t});
    return 0;
}

如果$map$里存结构体一定要把小于号重载写全,否则第一维相等就不插入了!

bool operator < (const Tri &a,const Tri &b)
{
    if(a.x==b.x&&a.y==b.y) return a.z<b.z;
    else if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}

C:

设$dp[i]$表示从$b+i$到$b$的步数，明显$dp[i]$是单调增的

这样每次贪心选取最小能达到的$a-amodc[i]$即可

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=1e5+10;
int n,dat[MAXN],a,b,res;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&dat[i]);
    sort(dat+1,dat+n+1);
    //必须离散化才能保证线性复杂度 
    n=unique(dat+1,dat+n+1)-dat-1;
    scanf("%d%d",&a,&b);
    
    while(a>b)
    {
        int mn=a-1;
        for(int i=1;i<=n;i++)
            if(a-a%dat[i]>=b) mn=min(mn,a-a%dat[i]);
        a=mn;res++;
        while(n&&a-a%dat[n]<b) n--;//一定要优化 
    }
    printf("%d",res);
    return 0;
}

注意一定要离散化+去除过大的$c[i]$进行优化！！

D:

E: