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_pairusing 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_pairusing 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;
}