A - Jin Yong’s Wukong Ranking List HihoCoder - 1870 题意： 给n条句子，每条句子有两个词，说明这两个词之间有一条边，判断这些边会不会形成一个环 题解： 一开始的想法是hash字符串离散化再dfs判环，但是交之后发现有bug，队友用map+floyd过了就没debug，但是我感觉这种做法应该也行，有空再仔细debug一下 队友的代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=25; #define endl '\n' map<string,int> M; string s1[N],s2[N]; int chart[N][N],sq; int A[N],B[N]; bool instack[N]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cout.setf(ios::fixed),cout.precision(3); int n; while(cin>>n){ M.clear(); memset(chart,0,sizeof(chart)); sq=0; bool flag=0; for(int i=1;i<=n;i++){ cin>>s1[i]>>s2[i]; if(!M.count(s1[i])) M[s1[i]]=++sq; if(!M.count(s2[i])) M[s2[i]]=++sq; A[i]=M[s1[i]]; B[i]=M[s2[i]]; chart[A[i]][B[i]]=1; if(flag) continue; for(int k=1;k<=sq;k++) chart[k][k]=1; for(int k=1;k<=sq;k++){ for(int p=1;p<=sq;p++){ for(int q=1;q<=sq;q++){ if(chart[p][k]&&chart[k][q]) chart[p][q]=1; } } } if(chart[B[i]][A[i]]) { flag=1; cout<<s1[i]<<" "<<s2[i]<<endl; } } if(!flag) cout<<0<<endl; } return 0; }D - Frog and Portal HihoCoder - 1873 题意： 一只青蛙初始坐标为0，一次能跳一个或两格，这样从0到200的方案数就是斐波那契的第200个数，但是现在可以设立无数个从一个点到另一个点的传送门，现给一个方案数，求设立的传送门的数量和位置 题解： 一开始用凑斐波那契数乘法与加法的想法考虑了很久，但是传送门数量一直大于200，最少也在200多，于是陷入了死胡同。最后看题解发现有比较巧妙的解法 设当前点为now 若当前方案数为奇数，设一个now到199的传送门使方案数-1，now点跳到now+2，这样方案数就会变成偶数 若当前方案数为偶数，则设now+1到now的传送门，now到now+2的传送门，则当前方案数会减半，因为不管从now到now+1还是到now+2，最后都会到达now+2
#pragma GCC optimize(3) #include <bits/stdc++.h> //#include <windows.h> #define ull unsigned long long #define ll long long #define pi 3.1415926 #define pll pair<ll,ll> #define pii pair<int,int> #define endl '\n' #define eps 1e-6 #define MP make_pair using namespace std; const int inf=0x3f3f3f; const int maxn=50; const int mod=1e9+7; int main() { ios::sync_with_stdio(false); ll M; while(cin>>M) { vector<pair<int,int>>v; if(M==0) { cout<<"2"<<endl<<"1 1"<<endl<<"2 1"<<endl; } else if(M==1) { cout<<"2"<<endl<<"1 199"<<endl<<"2 2"<<endl; } else { int now=1; while(M!=1) { if(M%2) { v.push_back(MP(now,199)); now+=2; } v.push_back(MP(now+1,now)); v.push_back(MP(now,now+2)); now+=3; M/=2; } v.push_back(MP(now-1,199)); cout<<v.size()<<endl; vector<pair<int,int>>::iterator it; for(it=v.begin();it!=v.end();it++) { cout<<it->first<<" "<<it->second<<endl; } } } return 0; }I - Palindromes HihoCoder - 1878 题意： 输入n，打印第n个回文串：1,2,3,4,5,6,7,8,9,11,22,33… 题解： 打表找规律，对于小于101的回文，直接输出，对于大于101的回文，则为： 若首位不为1，则首位为n-1，除了中间数，剩下的数翻转 若首位为1，判断第二位是否为10，若为10，则首位为9，除了10，中间数，剩下的数翻转
#pragma GCC optimize(3) #include <bits/stdc++.h> //#include <windows.h> #define ull unsigned long long #define ll long long #define pi 3.1415926 #define pll pair<ll,ll> #define pii pair<int,int> #define endl '\n' #define eps 1e-6 #define MP make_pair using namespace std; const int inf=0x3f3f3f; const int maxn=50; const int mod=1e9+7; int uns[25]={0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101}; int pw(int x) { int ans=1; for(int i=0;i<x;i++) { ans*=10; } return ans; } int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { string k,ans=""; cin>>k; int len=k.length(); if(len<=2) { int q=0; for(int i=0;i<len;i++) { q+=(k[i]-'0')*pw(len-i-1); } if(q<=20) { cout<<uns[q-1]<<endl; } else { k[0]-=1; for(int i=len-2;i>=0;i--) { k+=k[i]; } cout<<k<<endl; } } else { if(k[0]=='1'&&k[1]=='0') { ans+='9'; for(int i=2;i<len;i++) { ans+=k[i]; } len--; for(int i=len-2;i>=0;i--) { ans+=ans[i]; } cout<<ans<<endl; } else if(k[0]=='1') { for(int i=1;i<len;i++) { ans+=k[i]; } len--; for(int i=len-1;i>=0;i--) { ans+=ans[i]; } cout<<ans<<endl; } else { k[0]-=1; for(int i=len-2;i>=0;i--) { k+=k[i]; } cout<<k<<endl; } } } return 0; }