传送门 诶比赛打得贼爽，遇到了travel poorly 最后以一吨罚时，10/11题提前两小时结束比赛滚回宿舍了 随便整理一下题目吧 A 题意：需要烤 n (n<=500)条鱼，每次能烤 k 条鱼的一面，询问至少需要烤多少次才能烤完所有的鱼。（每条鱼的两面都需要被烤） 解答：直接输出2nk，和2取最大值，向上取整。
#include <bits/stdc++.h> using namespace std; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n,k; cin >> n >> k; cout << max( 2, (int)ceil( (double)2*(double)n/(double)k ) ); return 0; }B 题意：经典汉诺塔操作，询问在进行到多少步的时候第一次出现三个柱子上的圆盘数量相等，圆盘数 n<=300 解答：打表找规律 奇数项推偶数项： f(x)=4f(x−1)+4f(x−2)−16f(x−3)−21 偶数项推奇数项： f(x)=4f(x−1)+2 诶没想到这么奇葩的数列规律也能被我们找到 剩下的就是高精度了
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> using namespace std; const int MAXN = 410; struct bign { int len, s[MAXN]; bign () { memset(s, 0, sizeof(s)); len = 1; } bign (int num) { *this = num; } bign (const char *num) { *this = num; } bign operator = (const int num) { char s[MAXN]; sprintf(s, "%d", num); *this = s; return *this; } bign operator = (const char *num) { for(int i = 0; num[i] == '0'; num++) ; //ȥǰµ¼0 len = strlen(num); for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; return *this; } bign operator + (const bign &b) const //+ { bign c; c.len = 0; for(int i = 0, g = 0; g || i < max(len, b.len); i++) { int x = g; if(i < len) x += s[i]; if(i < b.len) x += b.s[i]; c.s[c.len++] = x % 10; g = x / 10; } return c; } bign operator += (const bign &b) { *this = *this + b; return *this; } void clean() { while(len > 1 && !s[len-1]) len--; } bign operator * (const bign &b) //* { bign c; c.len = len + b.len; for(int i = 0; i < len; i++) { for(int j = 0; j < b.len; j++) { c.s[i+j] += s[i] * b.s[j]; } } for(int i = 0; i < c.len; i++) { c.s[i+1] += c.s[i]/10; c.s[i] %= 10; } c.clean(); return c; } bign operator *= (const bign &b) { *this = *this * b; return *this; } bign operator - (const bign &b) { bign c; c.len = 0; for(int i = 0, g = 0; i < len; i++) { int x = s[i] - g; if(i < b.len) x -= b.s[i]; if(x >= 0) g = 0; else { g = 1; x += 10; } c.s[c.len++] = x; } c.clean(); return c; } bign operator -= (const bign &b) { *this = *this - b; return *this; } bign operator / (const bign &b) { bign c, f = 0; for(int i = len-1; i >= 0; i--) { f = f*10; f.s[0] = s[i]; while(f >= b) { f -= b; c.s[i]++; } } c.len = len; c.clean(); return c; } bign operator /= (const bign &b) { *this = *this / b; return *this; } bign operator % (const bign &b) { bign r = *this / b; r = *this - r*b; return r; } bign operator %= (const bign &b) { *this = *this % b; return *this; } bool operator < (const bign &b) { if(len != b.len) return len < b.len; for(int i = len-1; i >= 0; i--) { if(s[i] != b.s[i]) return s[i] < b.s[i]; } return false; } bool operator > (const bign &b) { if(len != b.len) return len > b.len; for(int i = len-1; i >= 0; i--) { if(s[i] != b.s[i]) return s[i] > b.s[i]; } return false; } bool operator == (const bign &b) { return !(*this > b) && !(*this < b); } bool operator != (const bign &b) { return !(*this == b); } bool operator <= (const bign &b) { return *this < b || *this == b; } bool operator >= (const bign &b) { return *this > b || *this == b; } string str() const { string res = ""; for(int i = 0; i < len; i++) res = char(s[i]+'0') + res; return res; } }; istream& operator >> (istream &in, bign &x) { string s; in >> s; x = s.c_str(); return in; } ostream& operator << (ostream &out, const bign &x) { out << x.str(); return out; } bool vis[305]; bign f[305]; bign F(int x) { if (x == 1) return 2; if (x == 2) return 9; if (x == 3) return 38; if (vis[x]) return f[x]; vis[x] = 1; if (x % 2) return f[x] = (F(x-1) * 4 + 2); else { // cout << F(x-1) * 4 << "\n"; // cout << F(x-3) * 4 << "\n"; // cout << F(x-2) * 4 << "\n"; // cout << ( F(x-3) * 4 - F(x-2) ) * 4 << "\n"; return f[x] = ( F(x-1) * 4 + F(x-2) * 4 - F(x-3) * 16 - 21); } } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n; cin >> n; n /= 3; cout << F(n) << "\n"; return 0; }C 题意：给定一个h×w的矩阵，需要用2×2的矩阵去覆盖它，覆盖的矩阵可以重叠但至少需要露出一半的面积。询问最大能放多少个2×2矩阵并且给出一种方案 解法：摆出来的结果 被我们成为蛇形矩阵，感受一下吧
#include<bits/stdc++.h> #define N 500010 using namespace std; int n,m,i,j,tot,x[N],y[N]; int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); cin>>n>>m; if (n<2||m<2) return puts("0"),0; if (m&1){ for (i=1;i<n;i+=2){ ++tot; x[tot]=i; y[tot]=m-1; } --m; } for (i=n-1;i>1;i--) for (j=1;j<m;j+=2) ++tot,x[tot]=i,y[tot]=j; for (i=m-1;i>=1;i--) ++tot,x[tot]=1,y[tot]=i; cout<<tot<<"\n"; for (i=1;i<=tot;i++) cout<<x[i]<<" "<<y[i]<<"\n"; return 0; }D 题意：给定一个有4种字符WESN构成的字符串，并且有合法拆分SW,NW,SE,NE或者拆成单个字符串，求合法方案数 解法：签到dp
#include<stdio.h> #include<cstring> #define N 100005 #define mod 1000000007 char S[N]; int n,dp[N]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%s",S+1); n=strlen(S+1); dp[0]=1; for (int i=1;i<=n;i++) { dp[i]=(dp[i]+dp[i-1]) % mod; if ((S[i]=='W' || S[i]=='E') && (S[i-1]=='S' || S[i-1]=='N')) dp[i]=(dp[i]+dp[i-2]) % mod; } printf("%d",dp[n]); }EFGHJ 留坑待填
