第一次玩TC,感觉还不错,就是得熬夜不好。比赛前还做了点,练习下。
第一题,水题,秒杀
第二题,上走或右走,其实就是3进制下是不是都是连续的1,可以用异或判断,只适用div2。
但正解是搜索,上下左右跑。
第三题,树DP,看了下,以为不会,把树的理解错了,没出。
涨rating 1333 好像直接进div1了。
第一题
#line 2 "FoxAndWord.cpp" #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <vector> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define DWN(i,a,b) for(int i=a;i>=b;--i) #define clr(f,z) memset(f,z,sizeof(f)) using namespace std; class FoxAndWord { public: int howManyPairs(vector <string> words) { int ans = 0; int len = words.size(); FOR(i,0,len-1) FOR(j,i+1,len-1) if(OK(words[i],words[j])) ++ans; return ans; } bool OK(string a,string b) { string c; int len = a.size(); FOR(i,0,len-1) { c = ""; FOR(j,i,len-1) c += a[j]; FOR(j,0,i-1) c += a[j]; if(c == b) return 1; } return 0; } }; // BEGIN CUT HERE int main() { return 0; } // END CUT HERE第二题
#line 2 "FoxAndFencingEasy.cpp" #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <vector> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define DWN(i,a,b) for(int i=a;i>=b;--i) #define clr(f,z) memset(f,z,sizeof(f)) using namespace std; class FoxAndFencingEasy { public: int fabs(int x) { if(x<0) return -x; return x; } string WhoCanWin(int mov1, int mov2, int d) { string s; if(mov1>=d) s="Ciel"; else if(fabs(mov1-mov2)<=min(mov1,mov2)) { s="Draw"; } else if(mov1>mov2) s="Ciel"; else s="Liss"; return s; } }ts; // BEGIN CUT HERE int main() { int a,b,c; while(cin>>a>>b>>c) { cout<<ts.WhoCanWin(a,b,c)<<endl; } return 0; } // END CUT HERE
第三题
#line 2 "FoxConnection2.cpp" #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <vector> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define DWN(i,a,b) for(int i=a;i>=b;--i) #define clr(f,z) memset(f,z,sizeof(f)) #define LL long long using namespace std; const int MOD = 1e9+7; const int mm = 255; class Edge { public: int v,next; }; class FoxConnection2 { public: int N,M; Edge e[mm+mm]; int head[mm],edge; int dp[mm][mm]; bool vis[mm]; void clear() { clr(head,-1); edge = 0; } void add(int u,int v) { e[edge].v = v; e[edge].next = head[u]; head[u] = edge++; } void dfs(int u) { vis[u] = 1; int v; dp[u][0] = dp[u][1] = 1; for(int l=head[u];~l;l=e[l].next) { v = e[l].v; if(vis[v]) continue; dfs(v); DWN(i,M,2) FOR(j,1,i-1) { // cout<<u<<" uv "<<v<<"i="<<i<<" "<<dp[u][i]<<" "<<dp[u][i-j]<<" "<<dp[v][j]<<endl; dp[u][i] = (dp[u][i]+(LL)dp[u][i-j]*dp[v][j])%MOD; } } // cout<<"u M "<<u<<" "<<dp[u][M]<<endl; } int ways(vector <int> A, vector <int> B, int k) { clear(); N = A.size() + 1; M = k; FOR(i,0,A.size()-1) add(A[i],B[i]), add(B[i],A[i]); clr(dp,0); clr(vis,0); dfs(1); int ans = 0; FOR(i,1,N) { ans += dp[i][M]; if(ans > MOD) ans -= MOD; } // ans = dp[1][M]; return ans; } }solver; // BEGIN CUT HERE int main() { while(1) { int a,b; vector<int> A,B; while(cin>>a>>b) { if(a == -1 && b == -1) break; A.push_back(a); B.push_back(b); } cin>>a; cout<<"ans = "<<solver.ways(A,B,a)<<endl; } return 0; } // END CUT HERE