题解Codeforces Round #597 (Div. 2)（CF1245）

A：送分，裸的gcd。

#include<stdio.h> 
#define il inline
#define it register int
int T,a,b,d; 
il void  gcd(int a,int b){
    if(!b){d=a;return;}
    gcd(b,a%b);
}
il void fr(int &num){
    num=0;char c=getchar();int p=1;
    while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    num*=p;
}   
int main(){
    fr(T);
    while(T--)
        fr(a),fr(b),gcd(a,b),d==1?puts("Finite"):puts("Infinite");  
    return 0;
}

B：送分，直接把能用的都用掉就行。

#include<stdio.h>
#include<string.h>
#define it register int
#define il inline
using namespace std;
const int N=100005;
int T,n,a,b,c,ans;
char s[N],o[N]; 
il void fr(int &num){
    num=0;char c=getchar();int p=1;
    while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    num*=p;
}   
int main(){
    fr(T);
    while(T--){
        scanf("%d%d%d%d%s",&n,&a,&b,&c,s+1),ans=n;
        for(it i=1;i<=n;++i){
            if(s[i]=='S'&&a) --a,o[i]='R';
            else if(s[i]=='R'&&b) --b,o[i]='P';
            else if(s[i]=='P'&&c) --c,o[i]='S';
            else o[i]='K';
        } 
        for(it i=1;i<=n;++i)
            if(o[i]=='K'){
                if(a) o[i]='R',--a;
                else if(b) o[i]='P',--b;
                else if(c) o[i]='S',--c;
                --ans;
            }
        if(ans<((n+1)>>1)) puts("NO");
        else{
            puts("YES");
            for(it i=1;i<=n;++i) putchar(o[i]);putchar('
');
        }
    } 
    return 0;
}

C：送分，手玩一下发现每个块的贡献是斐波那契数列。而且好像这题之前CF出过的。

#include<stdio.h>
#include<string.h>
#define it register int
#define il inline
using namespace std; 
const int N=1000005;
const long long mod=1e9+7;
char s[N];
long long f[N],ans=1;
int n; 
il void fr(int &num){
    num=0;char c=getchar();int p=1;
    while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    num*=p;
}   
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    f[0]=f[1]=1,f[2]=2;for(it i=3;i<=n;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for(it i=1;i<=n;++i){
        if(s[i]=='u'||s[i]=='n'){
            it j;
            for(j=i;s[j]==s[i]&&j<=n;++j);
            ans=1ll*ans*f[j-i]%mod,i=j-1;
        }
        if(s[i]=='m'||s[i]=='w'){
            putchar('0');return 0;
        }
    }
    printf("%lld",ans);  
    return 0;
}

D：最小生成树，预处理每一对(i,j)的连边就行。n个点连通就跳出不做。而且这题据说是USACO某道原题。。

#include<stdio.h>
#include<algorithm>
#define it register int
#define il inline
using namespace std;
const int N=3005;
long long ans;
int n,o[N],o1[N],o2[N],c1,c2,fa[N],cnt,cnum;
struct ky{
    int l,r;long long num;
    bool operator<(const ky&p)const{
        return num<p.num;
    }
}a[N*N];
struct str{
    int x,y,c,k;
}b[N];
il int A(it x){
    return x<0?-x:x;
}
il int dis(it i,it j){
    return A(b[i].x-b[j].x)+A(b[i].y-b[j].y);
}
il int fd(it x){
    return fa[x]==x?x:fa[x]=fd(fa[x]);
}
il void fr(int &num){
    num=0;char c=getchar();int p=1;
    while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    num*=p;
}
int main(){
    fr(n);
    for(it i=1;i<=n;++i) fr(b[i].x),fr(b[i].y),fa[i]=i;fa[n+1]=n+1;
    for(it i=1;i<=n;++i) fr(b[i].c);
    for(it i=1;i<=n;++i) fr(b[i].k);
    for(it i=1;i<=n;++i){
        for(it j=i+1;j<=n;++j) a[++cnt]=(ky){i,j,1ll*dis(i,j)*(b[i].k+b[j].k)};
        a[++cnt]=(ky){n+1,i,b[i].c};
    }
    sort(a+1,a+1+cnt);
    for(it i=1,t1,t2;i<=cnt;++i){
        t1=fd(a[i].l),t2=fd(a[i].r);
        if(t1==t2) continue;
        fa[t1]=t2,ans+=a[i].num,++cnum,a[i].l<=n?o1[++c2]=a[i].l,o2[c2]=a[i].r:o[++c1]=a[i].r;
        if(cnum==n) break;
    }
    printf("%lld
%d
",ans,c1);
    for(it i=1;i<=c1;++i) printf("%d ",o[i]);
    printf("
%d
",c2);
    for(it i=1;i<=c2;++i) printf("%d %d
",o1[i],o2[i]);
    return 0;
}

E：不会。。由于自己看不下去自己过于颓废的样子所以对着jky大佬的题解研究了一下E的做法。。这里补上啦。更好的理解：jky大佬的blog

#include<stdio.h>
#define it register int
#define il inline
#define Min(a,b)(a<b?a:b)
typedef double db;
const int N=15;
const int n=10;
struct ky{
    int x,y;
}nxt[N][N];
db f[N][N];
int a[N][N];
db dfs(it x,it y){
    if(x==1&&y==1) return 0;
    if(f[x][y]>=0) return f[x][y];
    f[x][y]=0;it now=0;
    register double tans=0;register ky tp;
    for(it i=1,tx=x,ty=y;i<=6;++i){
        if(tx==1&&ty==1){
            now=7-i;break;
        }
        tp=nxt[tx][ty],tx=tp.x,ty=tp.y,tans=dfs(tx,ty);
        if(a[tx][ty]) tans=Min(tans,dfs(tx-a[tx][ty],ty));
        f[x][y]+=tans;
    }
    return f[x][y]=(f[x][y]+6.0)/(6.0-now);
}
int main(){
    for(it i=1;i<=n;++i)
        for(it j=1;j<=n;++j)
            f[i][j]=-1e6,scanf("%d",&a[i][j]),i&1?(j==1?nxt[i][j]=(ky){i-1,j}:nxt[i][j]=(ky){i,j-1}):(j==10?nxt[i][j]=(ky){i-1,j}:nxt[i][j]=(ky){i,j+1});
    printf("%.10lf",dfs(10,1)); 
    return 0;
}

F：数位dp。我不会告诉你我离正解只差一个特判的！

#include<stdio.h>
#include<string.h>
#define it register int
#define il inline 
using namespace std;
const int N=40;
typedef long long ll;
ll f[N][3][3],a[N],b[N],L,R,T; 
ll dfs(int now,int lim1,int lim2){
    if(now==-1) return 1;
    ll &ans=f[now][lim1][lim2];
    if(ans!=-1) return ans;
    ans=0;
    for(it i=0;i<=1;i++)
        for(int j=0;i+j<=1;j++)
            if((lim1||(i<=a[now])) && (lim2||(j<=b[now])))
                ans+=dfs(now-1,lim1|(i<a[now]),lim2|(j<b[now])); 
    return ans;
}
il ll cal(ll l,ll r){
    for(it i=30;i>=0;--i)
        a[i]=l>>i&1,b[i]=r>>i&1;
    memset(f,-1,sizeof(f));
    return dfs(30,0,0);
}    
il void fr(ll &num){
    num=0;char c=getchar();int p=1;
    while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    num*=p;
}  
int main(){
    fr(T);
    while(T--){
        fr(L),fr(R);register ll ans=cal(R,R); 
        if(L) ans=ans-2*cal(L-1,R)+cal(L-1,L-1);
        printf("%lld
",ans); 
    }
    return 0;
}

我还是菜啊，怎么大家纷纷切E，我就E不会怎么搞。。

而且。。用血的教训告诉大家：

1.数位dp，要判断l=0的情况，不可以盲减一。

2.交题目的时候手速要快，不要犹豫！否则你就是交不上去的那个人……

由于还在system testing 先放上我没有fst的几题的代码。

upd：补了下后面的