文章目录

ACM-ICPC北京赛区2018

A Jin Yong’s Wukong Ranking List

#include<bits/stdc++.h>

using namespace std;
const int maxn = 50;
vector<int>  G[maxn];
bool yes;
bool dfs(int node,int fa){
    for(int i = 0;i < (int) G[node].size(); ++i)
    {
        int v = G[node][i];
        if(v == fa) return true;
        if(dfs(v,fa)) return true;
    }
    return false;
}
int main(void){

    int n;
    while(cin>>n){
        for(int i = 1;i < maxn; ++i) G[i].clear();
        string s1,s2;
        map<string,int> ma;
        int tot = 1;
        string ans1,ans2;
        yes = true;
        for(int i = 1;i <= n; ++i){
            cin>>s1>>s2;
            if(ma[s1] == 0) ma[s1] = ++tot;
            if(ma[s2] == 0) ma[s2] = ++tot;
            int v = ma[s1],u = ma[s2];

            if(yes)
                {
                    if(dfs(u,v))
                    {
                        yes = false;
                        ans1 = s1,ans2 = s2;
                    }
                }
              G[v].push_back(u);
        }
        if(yes)
            puts("0");
        else
            cout<<ans1<<" "<<ans2<<endl;
    }



    return 0;
}

B Heshen’s Account Book

  • 前导零
  • 单独一个0
  • 接着上一行
  • 本行最后有空格
  • 好几行接到一起
  • 本行头部就是空格
  • 空行
#include<bits/stdc++.h>

using namespace std;
// 首先用fgets读取，处理行尾的换行
const int maxn = 1e3+10;
char ar[maxn];
string ans[maxn];
int  cnt[maxn];
vector<string> vec;
bool check(const string &s,int i)
{
    if(s.empty()) return false;
    if(s[0] == '0' && s.size() != 1)
        return false;
    for(int i = 0; i < (int)s.size(); ++i)
        if(!isdigit(s[i]))
            return false;
    ++cnt[i];
    vec.push_back(s);
    return true;
}
// void Gets(char *s){
// fgets(s,maxn,stdin);
// int n = strlen(s);
// if(s[n-1] == '\n'||s[n-1] == '\r')
// s[n-1] = 0;

// }
bool konghang(const string &s){
  for(int i = 0;i < (int) s.size(); ++i)
    if(s[i] != ' ')
      return false;
    return true;
}
int  main(void)
{
  // freopen("input.txt","r",stdin);
    // ios::sync_with_stdio(false);
    int  pre = 1;
    string s,s1,s2;
    int kase = 0;
    pre = 1;
    string backs;
    while(getline(cin,s))
    {
        ++kase; 
        if(konghang(s))
        {
          check(s2,pre);
          s2.clear();
          s1.clear();
          continue;
        }
        stringstream ss(s);
        ss >> s1;
        if(!konghang(backs) &&isdigit( backs[backs.size()-1]) && isdigit(s[0])){
            s2 += s1;
        }
        else
           check(s2,pre),pre = kase,s2 = s1;
        while(ss >> s1)
        {
          check(s2,pre);
          s2 = s1;
          pre  = kase;    
        }
        backs = s;
    }
    check(s2,pre);
    for(int i = 0;i < (int)vec.size(); ++i){
      cout<<vec[i];
      if(i == (int) vec.size() -1)
        cout<<('\n');
      else
        cout<<(' ');
    }
    for(int i = 1;i <= kase;++i)
      cout<<cnt[i]<<endl;
    return 0;
}

F Frog and Portal

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;
    typedef long long LL;
LL F[maxn];
int ans[maxn];
const int maxm = 500;
LL sum[maxm];
bool vis[maxm];
typedef pair<int,int>P;
bool process(LL n){
    int idx = 0;
    int sum = 0;
     for(int i = maxn-1;i >= 1; --i){
            if(n >= F[i]){
                // cout<<F[i]<<" "<<F[i+1]<<endl;
                n -= F[i];
                ans[i] = 1;
                idx = max(idx,i);
                sum += i;
                // cout<<i<<endl;
            }
            else
                ans[i] = 0;
        }
        return n == 0;
}
void solve(LL n){
      LL nn = n;
      if(n == 0){
         printf("2\n1 1\n2 1\n");
         return ;
        }
        int idx = 0;
        // int sum = 0;
        for(int i = maxn-1;i >= 1; --i){
            if(n >= F[i]){
                // cout<<F[i]<<" "<<F[i+1]<<endl;
                n -= F[i];
                ans[i] = 1;
                idx = max(idx,i);
                // sum += i;
                // cout<<i<<endl;
            }
            else
                ans[i] = 0;
        }

        // cout<<sum<<endl;
        vector<P> v;
        int cnt = 0;
        // c
        int l = 0;
        for(int i = 1;i <= idx; ++i){
            if(!ans[i]) continue;
            v.push_back(P(1+i+4*cnt,5+i+4*cnt));
            v.push_back(P(3+i+4*cnt,199));
            v.push_back(P(4+i+4*cnt,6+i+4*cnt));
            // v.push_back(P(1+i+4*cnt-1,5+i+4*cnt-1));
            // v.push_back(P(3+i+4*cnt-1,199));
            l = 6+i+4*cnt;
            cnt++;
        }
        v.push_back(P(l,l));
        v.push_back(P(l+1,l+1));
        sort(v.begin(),v.end());
        cout<<v.size()<<endl;
        for(auto c:v){
            cout<<c.first<<" "<<c.second<<endl;

        }
    }

int main(void){
    LL n;
    F[0] = 1;
    F[1] = 1;
    for(int i = 2; i < maxn;++i)
      {
          F[i] = F[i-1]+F[i-2];
      }
    while(~scanf("%lld",&n)){
        memset(ans,0,sizeof(ans));
        solve(n);
    }   




    return 0;
}

I Palindromes


const int maxn = 100000+10;
char ar[maxn];
char br[maxn];
// 首先确定最高位
// 
int main(void)
{
     
    // pow10[0] = 1;
    // for(int i = 1;i < maxn; ++i)
    // pow10[i] = pow10[i]*10;
    int    T;
    cin>>T;
    while(T--){
        memset(ar,0,sizeof(0));
        scanf("%s",ar);
        int n = strlen(ar);
        int t = (ar[1]-'0')+(ar[0]-'0')*10;
        if(n == 1){
            printf("%c\n",ar[0]-1);
            continue;
        }
        else if(n == 2){
            // int t = (ar[1]-'0')+(ar[0]-'0')*10;
            if(t == 10){
                printf("%d\n",9);
                continue;
            }
            if(t < 20){
                printf("%d%d\n",t-10,t-10);
                continue;
            }
        }
        //偶数
        
        if(t >= 11 &&t <= 19){
            t -= 11;
            printf("%d",t+1);
            printf("%s",ar+2);
            for(int i = n-1;i >= 2; --i) putchar(ar[i]);
            printf("%d",t+1);
        }
        // 奇数
        else{
            if(t == 10){
                t -= 2;
                printf("%d",t+1);
                printf("%s",ar+2);
                for(int i = n-2;i >= 2; --i)
                    putchar(ar[i]);
                printf("%d",t+1);
            }
            else {
                t = ar[0]-'0'-2;
                printf("%d",t+1);
                printf("%s",ar+1);
                for(int i = n-2;i >= 1; --i)
                    putchar(ar[i]);
                printf("%d",t+1);
            }
        }
        puts("");
    }
    return 0;
}