A.字符画

签到

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2163

#include
      
       using namespace std;int w;void go(){    for(int i=1;i<=w;i++)            cout<<".";}int main(){    cin>>w;        cout<<"ooo";        go();        cout<<"ooo";        go();        cout<<"ooo";        go();        cout<<"ooo\n";        cout<<"..o";        go();        cout<<"o.o";        go();        cout<<".o.";        go();        cout<<"o.o\n";        cout<<"ooo";        go();        cout<<"o.o";        go();        cout<<".o.";        go();        cout<<"ooo\n";        cout<<"o..";        go();        cout<<"o.o";        go();        cout<<".o.";        go();        cout<<"o.o\n";        cout<<"ooo";        go();        cout<<"ooo";        go();        cout<<"ooo";        go();        cout<<"ooo\n";    return 0;}
      

 

B.2018

打表规律

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2164

#include
      
       #define LL long longusing namespace std;LL dp[2005][2005];int main(){    int n,m;    for(int i=1;i<=2000;i++){        dp[1][i]=dp[i][1]=i;    }    for(int i=2;i<=2000;i++)        for(int j=2;j<=2000;j++){            dp[i][j]=dp[i-1][j]+dp[i][j-1]+1;            dp[i][j]=dp[i][j]%1000000007;        }        while(~scanf("%d %d",&n,&m)){            printf("%lld\n",dp[n][m]*dp[n][m]%1000000007);        }    return 0;}
      

 

C.时间旅行

读题签到

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2165

#include
      
       #define LL long longusing namespace std;int main(){    int n,m;    while(~scanf("%d %d",&n,&m)){        if(n>m) cout<
       
        <<"\n";        else cout<
        
         <<"\n";    }    return 0;}
        
       
      

 

D.卖萌表情包

贪心，找到表情优先级即可

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2166

#include
      
       #define LL long longusing namespace std;char s[1005][1005];bool vis[1005][1005];void go(int i,int j){    vis[i][j]=1;}int main(){    int n,m;    while(~scanf("%d %d",&n,&m)){        int ans=0;        memset(vis,0,sizeof(vis));                memset(s,0,sizeof(s));        for(int i=1;i<=n;i++)            scanf("%s",s[i]+1);        for(int i=1;i<=n;i++){            for(int j=1;j<=m;j++){                if(vis[i][j]) continue;                if(s[i][j]=='^'){                    if(!vis[i+1][j-1]&&!vis[i+1][j+1]&&s[i+1][j-1]=='v'&&s[i+1][j+1]=='v'){                        go(i+1,j-1);                        go(i+1,j+1);                        go(i,j);                        ans++;                    }else if(!vis[i][j+2]&&!vis[i+1][j+1]&&s[i][j+2]=='^'&&s[i+1][j+1]=='v'){                        ans++;                        go(i,j+2);                        go(i+1,j+1);                        go(i,j);                    }                }                else if(s[i][j]=='<'){                    if(!vis[i-1][j+1]&&!vis[i+1][j+1]&&s[i+1][j+1]=='>'&&s[i-1][j+1]=='>'){                        ans++;                        go(i+1,j+1);                        go(i-1,j+1);                        go(i,j);                    }                    else if(!vis[i+1][j+1]&&!vis[i+2][j]&&s[i+1][j+1]=='>'&&s[i+2][j]=='<'){                        ans++;                        go(i+2,j);                        go(i+1,j+1);                        go(i,j);                    }                }             }        }        cout<
       
        <<"\n";    }    return 0;}
       
      

 

J.买一送一

因为题目是一棵树，u点的贡献 == u(fa）的贡献 + 商品的总数 -（第一次出现此商品前的商品个数）

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2172

#include
      
       #define LL long longusing namespace std;vector
       
         v[100005];int a[100005];LL f[100005];int vis[100005];int pre[100005];void dfs(int u,int cnt){        for(int i=0;i<(int)v[u].size();i++){            int to=v[u][i];            if(!vis[a[u]]) cnt++;            vis[a[u]]++;            f[to]=f[u]+cnt-pre[a[to]];            int hv=pre[a[to]];            pre[a[to]]=cnt;            dfs(to,cnt);            if(--vis[a[u]]==0) cnt--;            pre[a[to]]=hv;        }}int main(){    int n;    while(~scanf("%d",&n)){            for(int i=1;i<=n;i++) v[i].clear();            memset(vis,0,sizeof(vis));            memset(f,0,sizeof(f));            memset(pre,0,sizeof(pre));        for(int i=2;i<=n;i++){            int u;            scanf("%d",&u);            v[u].push_back(i);        }        for(int i=1;i<=n;i++) scanf("%d",&a[i]);                    dfs(1,0);        for(int i=2;i<=n;i++)             printf("%lld\n",f[i]);    }    return 0;}
       
      

 

K.Use FFT 

我们将多项式a * 多项式b 得出如下

a0*b0 a0*b1 a0*b2 a0*b3      等于a0 * b3前缀和

　　　a1*b0 a1*b1 a1*b2　　等于a1 *b2前缀和

　　　　　　a2*b0 a2*b1

　　　　　　　　　a3*b0

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2173

#include
      
       #define LL long long#define mod 1000000007using namespace std;LL a[500005],b[500005];LL sum[1000005];int main(){    int n,m,l,r;    while(~scanf("%d %d %d %d",&n,&m,&l,&r)){        for(int i=1;i<=n+1;i++)                 scanf("%lld",&a[i]);        for(int i=1;i<=m+1;i++){            scanf("%lld",&b[i]);            sum[i]=(sum[i-1]+b[i]+mod)%mod;        }        for(int i=m+2;i<=r+1;i++)            sum[i]=sum[i-1];        LL ans=0;        for(int i=1;i<=n+1;i++){            ans=(ans+a[i]*(sum[r+1]-sum[l]+mod)%mod+mod)%mod;            if(l>0) l--;            if(r>=0) r--;             else break;        }        printf("%lld\n",(ans+mod)%mod);    }    return 0;}
      

 

 

H.千万不要用树套树

对于每个查询 答案等于 -1r左边的线段个数 + l+1右边的线段个数（这样就不会重复）

我们用两个线段树维护 一个维护左线段 一个维护右线段

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2170

#include
      
       #define LL long long#define mod 1000000007#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn = 100005;int sum1[maxn<<2],sum2[maxn<<2],cnt[maxn];void update1(int l,int r,int rt,int pos){    if(l==r){        sum1[rt]+=1;        return ;    }    int m=(l+r)>>1;    if(pos<=m) update1(lson,pos);    else update1(rson,pos);    sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1];}void update2(int l,int r,int rt,int pos){    if(l==r){        sum2[rt]+=1;        return ;    }    int m=(l+r)>>1;    if(pos<=m) update2(lson,pos);    else update2(rson,pos);    sum2[rt]=sum2[rt<<1]+sum2[rt<<1|1];}int query1(int l,int r,int rt,int L,int R){    if(L<=l&&r<=R){        return sum1[rt];    }    int m=(l+r)>>1;    int ans=0;    if(L<=m) ans+=query1(lson,L,R);    if(R>m) ans+=query1(rson,L,R);    return ans;}int query2(int l,int r,int rt,int L,int R){    if(L<=l&&r<=R){                return sum2[rt];    }    int m=(l+r)>>1;    int ans=0;    if(L<=m) ans+=query2(lson,L,R);    if(R>m) ans+=query2(rson,L,R);    return ans;}int main(){    int  n,q;    while(~scanf("%d %d",&n,&q)){        int all=0;        for(int i=1;i<=n*4;i++){             if(i<=n) cnt[i]=0;             sum1[i]=sum2[i]=0;        }        while(q--){            int op,l,r;            scanf("%d",&op);            if(op==1){                scanf("%d %d",&l,&r);                if(l==r) cnt[l]++;                update1(1,n,1,l);                update2(1,n,1,r);                all++;            }else {                scanf("%d %d",&l,&r);                int ans=all;                if(n>=l+1) {                       ans-=query1(1,n,1,l+1,n);                }                if(r-1>=1) {                     ans-=query2(1,n,1,1,r-1);                }                if(r-l==2) ans+=cnt[l+1];                printf("%d\n",ans);            }        }    }    return 0;}