2018ICPC 北京

ゝ一世哀愁。 2023-10-11 13:28 63阅读 0赞

A.0:27:15 solved by hl

感人的数据范围，每次连上边之后dfs一下前者看能不能找到自己就行

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

#include <iostream>
    #include <string>
    #include <map>
    #include <vector>
    #include <cstdio>
    using namespace std;
    int N;
    const int maxn = 110;
    map<string,int>Hash;
    vector<int>P[maxn];
    bool vis[maxn];
    int s;
    bool dfs(int t){
        vis[t] = 1;
        for(int i = 0 ; i < P[t].size(); i ++){
            int v = P[t][i];
            if(v == s) return false;
            if(vis[v]) continue;
            if(!dfs(v)) return false;
        }
        return true;
    }
    int main()
    {
       while(~scanf("%d",&N)){
            int cnt; cnt = 0; Hash.clear();
            for(int i = 0 ; i < maxn; i ++) P[i].clear();
            int flag = 0;
            for(int i = 1; i <= N; i ++){
                string a,b; cin >> a >> b;
                if(flag) continue;
                if(!Hash[a]) Hash[a] = ++cnt;
                if(!Hash[b]) Hash[b] = ++cnt;
                P[Hash[a]].push_back(Hash[b]);
                for(int j = 0; j < maxn; j ++) vis[j] = 0;
                s = Hash[a];
                if(!dfs(Hash[a])){
                    cout << a << " " << b << endl;
                    flag = 1;
                }
            }
            if(!flag) puts("0");
       }
        return 0;
    }

B.2:34:44(-6) solved by hl,gbs

debug题,两个人各写了一遍各WA了几发，最后提出0没有前导0的问题让两份代码都过了

先将所有串拼成一个很长的字符串，如果前一行末尾和后一行开头有一个不是数字，就要在两者之间加上空格

拼完之后就是一个简单的按题目统计了，对于每行出现的次数，要用一个数组记录一下每个字符串拼起来之后的断点

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

#include <iostream>
    #include <string>
    #include <map>
    #include <vector>
    #include <cstdio>
    #include <sstream>
    #include <algorithm>
    using namespace std;
    int N;
    const int maxn = 10010;
    string tmp,a;
    int id[maxn];
    int num[maxn];
    int main()
    {
        getline(cin,a); int cnt = 1;
        for(int i = 0 ; i < a.size(); i ++){
            if(a[i] != ' ') id[1]++;
        }
        while(getline(cin,tmp)){
            cnt++;
            if(!isdigit(a[a.size() - 1]) || !isdigit(tmp[0])){
                a.push_back(' ');
            }
            id[cnt] = id[cnt - 1];
            for(int i = 0 ; i < tmp.size(); i ++){
                if(tmp[i] != ' ') id[cnt]++;
            }
            a = a + tmp;
        }
       // cout << a << endl;
        stringstream ss(a);
        int sum = 0;
        int fi = 0 ;
        while(ss >> tmp){
            //cout << tmp << endl;
            int flag = 1;
            if(tmp[0] == '0' && tmp.size() > 1) flag = 0;
            if(islower(tmp[0]) || islower(tmp[tmp.size() - 1])) flag = 0;
            if(flag){
                int p = upper_bound(id + 1,id + 1 + cnt,sum) - id;
                num[p]++;
                if(!fi) fi = 1;
                else cout << " ";
                cout << tmp;
            }
            sum += tmp.size();
        }
        cout << endl;
        for(int i = 1; i <= cnt; i ++){
            printf("%d\n",num[i]);
        }
        return 0;
    }

solved by hl

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

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    char sum1[1000005];
    int ans[3005];
    
    int now_len1 = 0;
    int yuan;
    char lls1[1000005];
    int now_row;
    int llen;
    bool if_first = true;
    inline bool if_d(char a)
    {
        if (a>'9')
            return false;
        if (a<'0')
            return false;
        return true;
    }
    bool if_OK;
    void end1()
    {
    
        lls1[llen] = 0;
        //cout<<lls1<<endl;
    
        if (llen != 0)
        {
            if (lls1[0] == '0' && llen != 1)
            {
                llen= 0;
                return ;
            }
            if (if_d(lls1[0])&& if_d(lls1[llen-1]) )
            {
          //cout<<"   &&   "<<llen<<endl;
                if (!if_first)
                {
                    printf(" ");
                }
    
                if_first = false;
                printf("%s",lls1);
                ans[yuan]++;
            }
        }
        llen =0;
    
    
    
    }
    
    int main()
    {
        char a1;
        while(scanf("%c",&a1)!= EOF)
        {
    
            sum1[now_len1++] = a1;
        }
        //cout<<sum1;
        now_row = 0;
        llen =0;
        memset(ans,0,sizeof(ans));
        for (int i=0;i<now_len1; i++)
        {
            //cout<<now_len1
            if (sum1[i] == ' ')
                end1();
            else if (sum1[i] == '\n')
            {
                if (sum1[i+1] != 0)
                    now_row++;
                if (i == 0)
                    end1();
                else if(if_d(sum1[i-1]) && if_d(sum1[i+1]))
                {
                    //cout<<"P"<<endl;
                }
                else
                    end1();
            }
            else
            {
                lls1[llen++] = sum1[i];
                if (llen == 1)
                {
                    yuan = now_row;
                    if_OK = true;
                }
                if (!if_d(sum1[i]))
                {
                    if_OK = false;
                }
    
            }
        }
        end1();
        cout<<endl;
        for (int i=0; i<=now_row; i++)
        {
            cout<<ans[i]<<endl;
        }
    
        return 0;
    }
    /*
    a19 01 17b
    12 bdc 13
    23 14 0 bc
    
    
    
    
    */

solved by gbs

D.1:30:06(-1) solved by zcz

是个构造,具体方法看代码

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

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    using namespace std;
    int vis[40];
    
    vector<int> ans[2];
    
    int main()
    {
        long long M;
        while(cin>>M)
        {
            if(M==0)
            {
                cout<<2<<endl;
                cout<<"1 1"<<endl;
                cout<<"2 2"<<endl;
                continue;
            }
            ans[0].clear();
            ans[1].clear();
            memset(vis,0,sizeof(vis));
            int l=1;
            int cnt=0;
            while(M)
            {
                if(M&1)
                {
                    cnt++;
                    vis[l]=1;
                }
                l++;
                M>>=1;
            }
            int t=1;
            int i=0;
            int num=0;
            while(cnt)
            {
                if(vis[t])
                {
                    ans[0].push_back(i+1);
                    ans[1].push_back(199);
                    num++;
                    //cout<<i+1<<' '<<199<<endl;
                    vis[t]=0;
                    cnt--;
                    i=i+2;
                }
                else
                {
                    ans[0].push_back(i+1);
                    ans[1].push_back(i+2);
                    num++;
                    //cout<<i+1<<' '<<i+2<<endl;
                    i=i+2;
                    t++;
                }
            }
            ans[0].push_back(i);
            ans[1].push_back(i);
            num++;
            //cout<<i<<' '<<i<<endl;
            cout<<num<<endl;
            for(int j=0;j<num;j++)
            {
                cout<<ans[0][j]<<' '<<ans[1][j]<<endl;
            }
        }
    
    
        return 0;
    }

H.3:57:53 solved by hl

将所给模式串分成N + 1个模式串

其中一个是原来的，另一个是变了一个字母的

dp\[i\]\[j\]表示i号模式串在以j位置结尾处出现的次数，每次容斥减掉前面出现过的次数

最后将每个dp\[i\]\[j\] \* 2 ^ (M - j)次方计入贡献，表示前面匹配成功之后后面就可以随便写

[9.5补：hl托更了两周的AC自动机标准解法][9.5_hl_AC]

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

#include <iostream>
    #include <string>
    #include <map>
    #include <cstring>
    #include <vector>
    #include <cstdio>
    #include <sstream>
    #include <algorithm>
    #define LL long long
    using namespace std;
    int N,M;
    const int maxn = 110;
    char str[maxn][maxn];
    LL dp[maxn][maxn];
    LL pow2[maxn],sum[maxn];
    int main()
    {
        int T; scanf("%d",&T);
        for(int i = 0; i <= 40; i ++) pow2[i] = (1LL << i);
        while(T--){
            memset(dp,0,sizeof(dp));
            memset(sum,0,sizeof(sum));
            scanf("%d%d",&N,&M);
            scanf("%s",str[0] + 1);
            dp[0][N] = 1;
            for(int i = 1; i <= N; i ++){
                for(int j = 1; j <= N ; j ++) str[i][j] = str[0][j];
                if(str[i][i] == '0') str[i][i] = '1';
                else str[i][i] = '0';
                dp[i][N] = 1;
            }
             if(M < N){
                puts("0");
                continue;
            }
            sum[N] = (N + 1);
            for(int i = N + 1; i <= M ; i ++){
                for(int j = 0 ; j <= N ; j ++){
                    dp[j][i] = pow2[i - N] - sum[i - N];
                   // cout << dp[j][i] << endl;
                    for(int k = 0; k <= N ; k ++){
                      //  if(k == j) continue;
                        for(int l = 2; l <= N ; l ++){
                            int num = 0;
                            for(int p = l; p <= N && num < 1; p ++){
                                if(str[k][p] != str[j][p - l + 1]) num++;
                            }
                            if(num < 1){
                                dp[j][i] -= dp[k][i - l + 1];
                           //     cout << j << ' ' << k << " " << dp[k][i - l + 1] << " " << i - l + 1 << endl;
                            }
    
                        }
                    }
                   // cout << j << " " << i << " " << dp[j][i] << endl;
                    sum[i] += dp[j][i];
                }
                sum[i] += sum[i - 1] * 2;
              //  cout << sum[i] << endl;
            }
            LL ans = 0;
            for(int i = 0; i <= N ; i ++){
                for(int j = N ; j <= M ; j ++){
                    ans += dp[i][j] * pow2[M - j];
                }
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

I.1:19:19 solved by gbs

是个找规律，也可以推式子

具体规律看代码

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

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    /*
    int anz[45];
    int an0[45];
    
    
    
    void dfs(int n)
    {\
        int lln1 =n;
        INT T1;
    
        for (int i=0; i<20; i++)
        {
            if (lln1 <=anz[i])
            {
                if (i == 0)
                    cout<<lln1-1;
                else if (i == 1)
                    cout<<lln1<<lln1;
                else
                {
                    t1 =lln1/anz[i-2];
                    t1++;
                    cout<<t1;
                    ans[now_b++] = t1;
                    dfs();
    
                }
                return;
            }
            lln1 -= anz[i];
        }
    
    }*/
    char str1[100005];
    int ans[200005];
    int now_b;
    int main()
    {
        /*anz[0] = an0[0] = 10;
        anz[1] = 9;
        an0[1] = 10;
        for (int i=2; i<20; i++)
        {
            anz[i] = an0[i-2]*9;
            an0[i] = an0[i-2]*10;
            cout<<anz[i]<<endl;
        }*/
        int T;
        //int n;
        cin >>T;
        while(T--)
        {
            scanf("%s",str1);
            int len1 = strlen(str1);
            int t1;
            if (len1 == 1)
            {
                t1 = str1[0]-'0';
                t1--;
                cout<<t1<<endl;
                continue;
            }
            if (len1 == 2 &&str1[0] == '1'&&str1[1]=='0' )
            {
                cout<<9<<endl;
                continue;
            }
            if (str1[0] == '1'&&str1[1]>='1' )
            {
                t1 = str1[1] -'0';
                printf("%d",t1);
                for (int i=2; i<len1; i++)
                    printf("%c",str1[i]);
                for (int i=len1-1; i>=2; i--)
                    printf("%c",str1[i]);
                printf("%d\n",t1);
                continue;
            }
            if (str1[0] == '1' )
            {
                t1 = 9;
                printf("%d",t1);
                for (int i=2; i<len1; i++)
                    printf("%c",str1[i]);
                for (int i=len1-2; i>=2; i--)
                    printf("%c",str1[i]);
                printf("%d\n",t1);
                continue;
            }
            else
            {
                t1 = str1[0]-'1';
                printf("%d",t1);
                for (int i=1; i<len1; i++)
                    printf("%c",str1[i]);
                for (int i=len1-2; i>=1; i--)
                    printf("%c",str1[i]);
                printf("%d\n",t1);
                continue;
            }
    
    
        }
        return 0;
    }

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[9.5_hl_AC]: https://www.cnblogs.com/Hugh-Locke/p/11469819.html