2019 ICPC 徐州网络赛

分手后的思念是犯贱 2023-10-11 13:28 58阅读 0赞

A.00:45:42(-1) solved by zcz

队友说抄个板子好了，我看了一下板子是扩展中国剩余定理

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<climits>
    #include<cstring>
    #include<map>
    #include<algorithm>
    using namespace std;
    #define LL long long
    const int maxn=1e5+5;
    int n;
    LL exgcd(LL a,LL b,LL &x,LL &y){
        if(!b){x=1,y=0;return a;}
        LL re=exgcd(b,a%b,x,y),tmp=x;
        x=y,y=tmp-(a/b)*y;
        return re;
    }
    LL m[maxn],a[maxn];      //m为模数集，a为余数集
    LL exCRT(){
        LL M=m[1],A=a[1],t,d,x,y;int i;
        for(i=2;i<=n;i++){
            d=exgcd(M,m[i],x,y);//解方程
            if((a[i]-A)%d)return -1;//无解
            x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//求x
            A=M*x+A,M=M/d*m[i],A%=M;//日常膜一膜（划掉）模一模，防止爆
        }
        A=(A%M+M)%M;
        return A;
    }
    
    map<long long ,int> isF;
    
    
    
    
    int main()
    {
        long long f1=1,f2=1;
    
        while(f1<=1e16)
        {
            isF[f1]=1;
            long long t=f1;
            f1=f1+f2;
            f2=t;
    
        }
    
    
        int i,j;
        while(scanf("%d",&n)!=EOF){
            for(i=1;i<=n;i++)scanf("%lld%lld",&m[i],&a[i]);
            long long t=exCRT();
            if(t==-1)
            {
                cout<<"Tankernb!"<<endl;
                continue;
            }
            if(isF[t]==0)
            {
                cout<<"Zgxnb!"<<endl;
            }
            else
            {
                cout<<"Lbnb!"<<endl;
            }
        }
        return 0;
    }

B.00:11:42 solved by hl

范围小的话直接并查集，这题范围比较大，所以要离散化(雾)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

C.00:12:36(-3) solved by zcz

枚举题意，枚举到和出题人心意相通为止

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<map>
    using namespace std;
    
    int main()
    {
        int w;
        while(cin>>w)
        {
            if(w%2==0&&w>2)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        return 0;
    }

D.1:05:12 solved by hl

我就比较好奇，出这种题也有钱拿吗？

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

E.00:38:48 solved by hl

从后往前枚举，树状数组维护下标最大的值，树状数组下标为数的大小

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

F.03:14:29 solved by hl

本场唯一做的一道非签到题，提前感谢一下出题人

题目数据范围给的很奥妙重重，5000个询问和最多为100个k的情况仿佛在暗示什么

果不其然，一个询问点最多往上数100个祖先，枚举每个祖先作为lca对这个点产生的贡献，将会产生一个数的深度的范围，这个点的贡献是他所有子树中深度不超过某个数产生的，同时减去他的祖先对他的影响，每个询问就会变成至多100个询问。

求一个dfs序，题目就转化为了多次询问一个序列中区间所有大于等于p的数的权值和，把所有询问离线出来，用树状数组解决就好了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 2e6 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    LL a[maxn];
    struct Edge{
        int to,next;
    }edge[maxn * 2];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    int dep[maxn],p[maxn * 2],cnt,fa[maxn];
    PII pos[maxn];
    void dfs(int u,int la){
        pos[u].fi = ++cnt;
        p[cnt] = u;
        for(int i = head[u]; ~i; i = edge[i].next){
            int v = edge[i].to;
            if(v == la) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            dfs(v,u);
        }
        pos[u].se = ++cnt;
        p[cnt] = u;
    }
    struct Query{
        int l,r,id;
        int k,flag;
        Query(int l = 0,int r = 0,int id = 0,int k = 0,int flag = 0):l(l),r(r),id(id),k(k),flag(flag){}
    }q[maxn];
    int Stack[maxn];
    bool cmp(Query a,Query b){
        return a.k < b.k;
    }
    vector<int>Q[maxn];
    LL tree[maxn],ans[maxn];
    void add(int u,LL v){
        for(;u < maxn; u += u & -u) tree[u] +=v ;
    }
    LL getsum(int u){
        LL sum = 0;
        for(;u > 0; u -= u & -u) sum += tree[u];
        return sum;
    }
    int main(){
        Sca(N); init(); cnt = 0;
        for(int i = 1; i <= N ; i ++) a[i] = read();
        for(int i = 1; i <= N - 1; i ++){
            int u = read(),v = read();
            add(u,v); add(v,u);
        }
        dep[1] = 0; fa[1] = -1;
        dfs(1,-1);
        Sca(M); int o = 0;
        for(int i = 1; i <= M ; i ++){
            int u,w; Sca2(u,w);
            int j,root;
            Stack[0] = u;
            for(j = 0,root = u; j < w && fa[root] != -1;){
                root = fa[root];
                Stack[++j] = root;
            }
            int Mi = -1;
            for(int k = j ;k >= 0 ; k --){
                int v = Stack[k];
                int Mx = dep[v] + w - (dep[u] - dep[v]);
                if(Mi >= Mx) continue;
                if(Mi >= 0) q[++o] = Query(pos[v].fi,pos[v].se,i,Mi,-1);
                if(Mx >= 0) q[++o] = Query(pos[v].fi,pos[v].se,i,Mx,1);
                Mi = max(Mi,Mx); 
            }
        }
        sort(q + 1,q + 1 + o,cmp);
        int f = 1;
        for(int i = 1; i <= N ; i ++){
            Q[dep[i]].pb(i);
        }
        for(int i = 0; f <= o ; i ++){
            for(int j = 0 ; j < Q[i].size(); j ++){
                int v = Q[i][j];
                add(pos[v].fi,a[v]);
            }
            while(f <= o && q[f].k == i){
                ans[q[f].id] += getsum(q[f].l - 1) * -1 * q[f].flag;
                ans[q[f].id] += getsum(q[f].r) * q[f].flag;
                f++;
            }
        }
        for(int i = 1; i <= M; i ++){
            Prl(ans[i]);
        }
        return 0;
    }

G.00:50:53 solved by hl

回文树，bitset维护一下每个结点字母的数量直接冲就行了

不用bitset,建完树之后dfs统计也行，我寻思bitset可能会快一点，空间复杂度也顶住了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    const int maxn = 3e5 + 10;
    const int maxc = 26;
    struct Pal_T{
        int next[maxn][maxc];
        int fail[maxn],cnt[maxn],num[maxn],len[maxn],S[maxn];
        bitset<maxc>P[maxn];
        int last,n,tot;
        int newnode(int l){
            for(int i = 0 ; i < maxc; i ++) next[tot][i] = 0;
            cnt[tot] = num[tot] = 0;
            len[tot] = l;
            P[tot].reset();
            return tot++;
        }
        void init(){
            tot = 0; 
            newnode(0); //偶数根节点
            newnode(-1); //奇数根节点
            last = n = 0;
            S[n] = -1; fail[0] = 1;
        }
        int getfail(int x){
            while(S[n - len[x] - 1] != S[n]) x = fail[x];
            return x;
        }
        void add(int c){
            c -= 'a';
            S[++n] = c;
            int cur = getfail(last);
            if(!next[cur][c]){
                int now = newnode(len[cur] + 2);
                P[now] = P[cur];
                P[now][c - 'a'] = 1;
                fail[now] = next[getfail(fail[cur])][c];
                next[cur][c] = now;
                num[now] = num[fail[now]] + 1;
            }
            last = next[cur][c];
            cnt[last]++;
        }
        LL count(){
            LL ans = 0;
            for(int i = tot - 1; i >= 0; i --){
                cnt[fail[i]] += cnt[i];
                ans += 1ll * P[i].count() * cnt[i];
            } 
            return ans;
        }
    }PT;
    char str[maxn];
    int main(){
        scanf("%s",str); PT.init();
        for(int i = 0;str[i]; i ++) PT.add(str[i]);
        Prl(PT.count());
        return 0;
    }

I.2:01:19 solved by hl

因为原图是个全排列，可以证明即使将所有有关系的数连边，空间复杂度也是nlogn

这就变成了一个区间查询内部包含多少线段的问题了,简单的二位偏序问题，只要把E题敲完的树状数组复制过来就可以了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

J.2:11:54 solved by gbs

队友写的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #include <map>
    #include <set>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    typedef long long LL;
    const int maxn = 1e6 + 15;
    const int mod = 1e9 + 7;
    vector<int> pn[maxn + 15] ;
    int th_inv[maxn + 15] ;
    int high1[maxn+15];
    int quick_mi(LL a, LL k)
    {
        LL ans = 1;
        while (k)
        {
            if (k & 1)
            {
                ans *= a;
                ans %= mod;
            }
            a *= a;
            a %= mod;
            k >>= 1;
        }
        return ans;
    }
    int the_hight;
    int find_hight(int nowi,int fu)
    {
        int nowa = pn[nowi].size();
        if (fu != 0)
        {
            nowa--;
        }
        if (nowa == 0)
        {
            return high1[nowi] = 1;
        }
        for (unsigned int i=0; i<pn[nowi].size(); i++)
        {
            if (pn[nowi][i] == fu)
            {
                continue;
            }
            high1[nowi] = max(high1[nowi],find_hight(pn[nowi][i],nowi)+1);
        }
        return high1[nowi];
    }
    int inva(int a)
    {
        if (th_inv[a] == 0)
            return th_inv[a] = quick_mi(a,mod-2);
        return th_inv[a];
    }
    
    
    int the_ans(int nowi, int fu,int di)
    {
        int now_ans = 0;
        if (di + high1[nowi] != the_hight)
        {
            return 1;
        }
        int nowa = pn[nowi].size();
        if (fu != 0)
        {
            nowa--;
        }
        if (nowa == 0)
        {
            return 0;
        }
        for (unsigned int i=0; i<pn[nowi].size(); i++)
        {
            if (pn[nowi][i] == fu)
            {
                continue;
            }
            now_ans  = (0LL + now_ans  + the_ans(pn[nowi][i],nowi,di+1))%mod;
        }
        //cout<<nowi <<' '<<nowa<<' '<<now_ans <<endl;
        now_ans  = (1LL * now_ans  *inva(nowa))%mod;
        now_ans  = quick_mi(now_ans ,nowa);
        //cout<<"*"<<' '<<nowi<<' '<<now_ans <<endl;
        return now_ans ;
    
    }
    int main()
    {
        int n;
        int a, b;
        cin >> n;
        for (int i = 0; i < n-1; i++)
        {
            scanf("%d%d", &a, &b);
            pn[a].push_back(b);
            pn[b].push_back(a);
        }
        find_hight(1,0);
        the_hight = high1[1];
        //printf("%d\n",(the_ans(1,0,0)+mod)%mod  );
        printf("%d\n",(1-the_ans(1,0,0)+mod)%mod  );
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }

K.00:49:48 solved by gbs

队友写的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #include <map>
    #include <set>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    
    using namespace std;
    
    typedef long long LL;
    
    int xxnn[1005];
    int yynn[1005];
    struct pointa{
        int xi;
        int yi;
        pointa(int x1 =0,int y1 =0)
        {
            xi =x1;
            yi = y1;
        }
        bool operator <(const pointa & s1)const{
            if (xi!= s1.xi)
                return this->xi <s1.xi;
            return this->yi <s1.yi;
        }
        bool operator ==(const pointa & s1)const{
            return (this->xi ==s1.xi)&&(this->yi ==s1.yi);
        }
    
    };
    
    int main()
    {
        int n;
        cin >>n;
        map<pointa,int>s1;
        for (int i=0; i<n; i++)
        {
            scanf("%d%d",&xxnn[i],&yynn[i]);
            if (s1[pointa(xxnn[i],yynn[i])] >=1)
            {
                n--;
                i--;
                continue;
            }
            else
            {
                s1[pointa(xxnn[i],yynn[i])]=1;
                xxnn[i] *= 2;
                yynn[i] *= 2;
            }
            
            
        }
        int fin_ans = 0;
        int llx;
        int lly;
        map<pointa,int>map1;
        for (int i=0; i<n; i++)
        {
            for (int j=i; j<n; j++)
            {
                llx = (xxnn[i]+xxnn[j])/2;
                lly = (yynn[i]+yynn[j])/2;
                if (xxnn[i]==xxnn[j] && yynn[i]==yynn[j])
                {
                    map1[pointa(llx,lly)]+=1;
                }
                else
                {
                    map1[pointa(llx,lly)]+=2;
                }
                
                fin_ans = max(fin_ans,map1[pointa(llx,lly)]);
            }
        }
        printf("%d\n",n-fin_ans);
    
    
    
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }

L.3:36:27(-4) solved by zcz,hl

预处理出任意两点间，红点朝上翻滚到另一点红点朝上需要的步数

就是个旅行商问题了

状压dp入门门槛

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1 << 16;
    const LL INF = 1e18;
    const int mod = 1e9 + 7; 
    int N,M,K;
    LL dis[4005][4005];
    
    void init(){
        dis[0][0]=0;
        int k=3;
        int cnt=1;
        for(int i=1;i<=4000;i++)
        {
            if(cnt%4==0)
            {
    
                dis[i][0]=dis[0][i]=cnt;
            }
            else
            {
                dis[i][0]=k;
                dis[0][i]=k;
            }
            dis[i][1]=dis[1][i]=dis[i][0]+1;
            k++;
            cnt++;
        }
        for(int i=2;i<=4000;i++)
        {
            for(int j=2;j<=4000;j++)
            {
                dis[i][j]=i+j;
            }
        }
        dis[1][1]=6;
        dis[1][2]=dis[2][1]=5;
        dis[1][3]=dis[3][1]=6;
        dis[2][2]=4;
    } 
    PII node[20];
    LL MAP[20][20];
    LL dp[20][maxn];
    int main(){
        init();
        int T = read();
        while(T--){
            Sca(N);
            for(int i = 0; i < N ; i ++){
                node[i].fi = read();
                node[i].se = read();
            }
            for(int i = 0; i < N ; i ++){
                for(int j = 0; j < N ; j ++){
                    MAP[i][j] = dis[abs(node[i].fi - node[j].fi)][abs(node[i].se - node[j].se)];
                }
                MAP[N][i] = MAP[i][N] = dis[abs(node[i].fi)][abs(node[i].se)];
            }
            int ed = (1 << N);
            for(int i = 0 ; i <= N ; i ++){
                for(int j = 0 ; j < ed; j ++) dp[i][j] = INF;
            }
            dp[N][0] = 0;
            for(int i = 0 ; i < ed; i ++){
                for(int j = 0 ; j <= N ; j ++){
                    if(dp[j][i] == INF) continue;
                    for(int k = 0; k < N ; k ++){
                        if(i & (1 << k)) continue;
                        int v = i | (1 << k);
                        dp[k][v] = min(dp[k][v],dp[j][i] + MAP[j][k]);
                    }
                }
            }
            LL ans = INF;
            for(int i = 0 ; i < N ; i ++) ans = min(ans,dp[i][ed - 1]);
            Prl(ans);
        }
        return 0;
    }

M.01:47:31(-4) solved by hl

因为眼睛不好使子序列看成了子串，敲完EXKMP还WA了一发

发现a串只要比b串中的某个位置大，a串后面就都符合，前提是当前位置前面需要找的出子序列和b串位置的前缀一样

树状数组维护前缀最大值，表示a串比这个字符大的时候，前缀最多能匹配多少个数，答案就是max(N - i + 1 + max(0 ~ a\[i\]))

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

转载于:https://www.cnblogs.com/Hugh-Locke/p/11483449.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif