Wannafly挑战赛22-A/B/C

链接：https://www.nowcoder.com/acm/contest/160/A
来源：牛客网

题目描述

有一个计数器，计数器的初始值为0，每次操作你可以把计数器的值加上a₁,a₂,...,a_n中的任意一个整数，操作次数不限（可以为0次），问计数器的值对m取模后有几种可能。

　　　　令 g=gcd(a1,a2,,,,,,an) ,显然 (k*g)%m 的不同个数就是答案,观察之后发现这个式子是有循环节的，假设第一次出现循环的
位置是x，也就是说 x*g=0 (mod m) x*g+y*m=0 ,x的解 x=x0+k*(m/gcd(g,m)) ,其实答案就是 m/(gcd(g,m)。
　　

       
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
#include<map>
#include<set>

#include<bits/stdc++.h>
using namespace std;

#define LL long long 
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int t,n,m,i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF){
        LL ans=m,a;
        for(i=1;i<=n;++i){
            scanf("%lld",&a);
            ans=gcd(ans,a);
        }
        cout<<m/ans<<endl;
    }
    return 0;
}

 

链接：https://www.nowcoder.com/acm/contest/160/B
来源：牛客网

题目描述

给一个含n个点m条边的有向无环图（允许重边，点用1到n的整数表示），每条边上有一个字符，问图上有几条路径满足路径上经过的边上的字符组成的的字符串去掉空格后以大写字母开头，句号 '.' 结尾，中间都是小写字母，小写字母可以为0个。

输入描述:

第一行两个整数n,m
接下来m行，每行两个整数a,b和一个字符c，表示一条起点为a，终点为b的边，边上的字符是c
1 ≤ n, m ≤ 50000
1 ≤ a < b ≤ n
c可以是大小写字母、句号 '.' 或空格（方便起见用 '_' 表示空格）

　　　　
　　
　 ps:我想的复杂了，有个更简单的dp是 f[i][0/1/2/3]表示第i个节点结尾的，符号是j类型的合法子串的数目，这样就好写多了>_<.

　　先对这个DAG进行拓扑排序。　　
　　设置四个类型 0-[A-Z] 1-[a-z] 2-[.] 3-[_]     f[j][k1][k2]表示以第j个字符结尾的，开头是k1类型,结尾是k2类型的合法串的个数，答案就是SUM{f[i][0][2]}。转移的时候如果多个'_'连着算作一个就好了，如果有合法串与"__"拼接，那么直接略去'_'即可，也就是说长度大于1的串中不显示'_'，单独设置类型4只用作表示开头指代这个状态的子串长度是1.转移的时候我直接枚举所有情况，所以写的很长，其实很多状态都是无用的，但分析起来怕出错就直接写了。我转移的时候忘记了小写字母可以不存在，，比赛结束5min才发现然后1A......

       
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
#include<map>
#include<set>

#include<bits/stdc++.h>
using namespace std;

#define LL long long 
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define uint unsigned int
uint f[50050][5][5]={0};
vector<pii>e[50050];
vector<int>vi;
int in[50050];
void topsort(int n){
    queue<int>q;
    for(int i=1;i<=n;++i){
        if(!in[i]) {q.push(i);vi.push_back(i);}
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<e[u].size();++i){
            pii _e=e[u][i];
            if(!(--in[_e.first])){
                q.push(_e.first);
                vi.push_back(_e.first);
            }
        }
    }
    //for(i=0;i<n;++i)cout<<vi[i]<<endl;
}
void solve(int n){
    uint ans=0;
    for(int i=0;i<n;++i){
        int u=vi[i];
        for(int j=0;j<e[u].size();++j){
            f[e[u][j].first][4][e[u][j].second]++;
        }
            for(int k1=0;k1<=4;k1++){
                for(int k2=0;k2<4;++k2){
                    if(f[u][k1][k2]){
                        //cout<<u<<' '<<k1<<' '<<k2<<' '<<f[u][k1][k2]<<endl;
                        for(int j=0;j<e[u].size();++j){
                            //cout<<u<<' '<<e[u][j].first<<endl;
                            uint s=f[u][k1][k2];
                            if(e[u][j].second==0){
                            if(k1==4){
                                 if(k2==3)
                                    f[e[u][j].first][4][0]+=s;
                               }
                            }
                            else if(e[u][j].second==1){
                            if(k1==4){
                                if(k2==0){
                                    f[e[u][j].first][0][1]+=s;
                                }
                                else if(k2==3){
                                    f[e[u][j].first][4][1]+=s;
                                }
                            }
                            else{
                                if(k1!=0)continue;
                                if(k2==1)
                                    f[e[u][j].first][0][1]+=s;
                              }
                            }
                            else if(e[u][j].second==2){
                            if(k1==4){
                                if(k2==0){
                                    f[e[u][j].first][0][2]+=s;
                                }
                            }
                            else{
                                if(k1!=0)continue;
                                if(k2==1){
                                    f[e[u][j].first][0][2]+=s;
                                }
                            }
                            }
                            else{
                            if(k1==4){
                                if(k2==0){
                                    f[e[u][j].first][4][0]+=s;
                                }
                                else if(k2==3){
                                    f[e[u][j].first][4][3]+=s;
                                }
                            }
                            else{
                                if(k1!=0)continue;
                                if(k2==1){
                                    f[e[u][j].first][0][1]+=s;
                                }
                                else if(k2==2){
                                    f[e[u][j].first][0][2]+=s;
                                }
                            }
                            }
                        }
                    }
                }
            }
    }
    for(int i=1;i<=n;++i)ans+=f[i][0][2];
    cout<<ans<<endl;
}
int main(){
    int n,m;
    int u,v,w;
    char c;
    cin>>n>>m;
    while(m--){
        //scanf("%d%d%c",&u,&v,&c);
        cin>>u>>v>>c;
        if(c>='A'&&c<='Z') w=0;
        else if(c>='a'&&c<='z') w=1;
        else if(c=='.') w=2;
        else w=3;
        in[v]++;
        e[u].push_back(mp(v,w));
    }
    topsort(n);
    solve(n);
    return 0;
}

链接：https://www.nowcoder.com/acm/contest/160/D
来源：牛客网

题目描述

给出一个长度为n的整数序列a₁,a₂,...,a_n，进行m次操作，操作分为两类。
操作1：给出l,r,v，将a_l,a_l+1,...,a_r分别加上v；
操作2：给出l,r，询问

 

 

 

 

 

　　　　　　　　利用正弦和的公式  sin(a+b)=sin(a)cos(b)+cos(a)sin(b)   cos(a+b)=cos(a)cos(b)-sin(a)sin(b)，区间维护sin和cos的和。我在update函数里

一直没有写标记下方函数，后来才发现>_< ,标记是一定要下放的，之前没有考虑过这个问题，现在想想确实是这样，因为子区间更新完要pushup一下，

如果标记没有下放那么保存的结果在pushup的时候就会发生变化了，缺少了标记代表的值。

　　　　

       
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
#include<map>
#include<set>

#include<bits/stdc++.h>
using namespace std;

#define LL long long 
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (id<<1|1)
const int  maxn=200100;
double SIN[maxn<<2],COS[maxn<<2];
LL tag[maxn<<2];

void calc(int id,LL x){
    double t1=SIN[id],t2=COS[id],t3=sin(x),t4=cos(x);
    SIN[id]=t1*t4+t2*t3;
    COS[id]=t2*t4-t1*t3;
}
void pushup(int id){
    SIN[id]=SIN[lc]+SIN[rc];
    COS[id]=COS[lc]+COS[rc];
}
void pushdown(int id,int L,int R){
    if(tag[id]){
        calc(lc,tag[id]),calc(rc,tag[id]);
        tag[lc]+=tag[id],tag[rc]+=tag[id];
        tag[id]=0;
    }
}
void build(int id,int L,int R){
    if(L==R){
        LL x;scanf("%lld",&x);
        SIN[id]=sin(x),COS[id]=cos(x);
        return ;
    }
    build(lc,L,mid);
    build(rc,mid+1,R);
    pushup(id);
}
void add(int id,int L,int R,int l,int r,LL v){
    if(L>=l&&R<=r){
        calc(id,v);
        tag[id]+=v;
        return;
    }
    pushdown(id,L,R);
    if(l<=mid)add(lc,L,mid,l,r,v);
    if(r>mid) add(rc,mid+1,R,l,r,v);
    pushup(id);
}
double ask(int id,int L,int R,int l,int r){
    if(L>=l&&R<=r){
        return SIN[id];
    }
    pushdown(id,L,R);
    if(r<=mid) return ask(lc,L,mid,l,r);
    else if(l>mid) return ask(rc,mid+1,R,l,r);
    else return ask(lc,L,mid,l,r)+ask(rc,mid+1,R,l,r);
}
int main(){
    LL n,m,i,j,k,l,r;
    LL v;
    cin>>n;
    build(1,1,n);
    cin>>m;
    while(m--){
        scanf("%d",&k);
        if(k==1){
            scanf("%d%d%lld",&l,&r,&v);
            add(1,1,n,l,r,v);
        }
        else{
            scanf("%d%d",&l,&r);
            printf("%.1f
",ask(1,1,n,l,r));
        }
    }
    return 0;
}
/*
4
1 2 3 4
5
2 1 4
1 1 4 1
2 1 4
*/