A.给N个球和无限个盒子，可以每次依次执行如下操作： 1.加个空盒子 2.每个有球的盒子里各拿一个放到空盒子里 3.删除所有空盒子 4.排成非降序 5.得到一组结果 判断给定N个球能否在有限的次数内出现相邻两次结果，不能便输出小于N的最大可行数 思路：假设当前x个盒子，两次结果相同发生的变化是所有的盒子减1，移除空盒子，加一个为x的盒子，盒子当且仅当为1，2，…x时才可以实现，所以寻找小于等于N的K满足 K = i ∗ ( i + 1 ) 2 K=\frac{i*(i+1)}{2} K=2i∗(i+1)
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> using namespace std; #define ll long long int main() { int t; scanf("%d",&t); for(int h=1;h<=t;h++) { ll n; scanf("%lld",&n); ll i=sqrt(n*2); if(i+1<=n*2/i) printf("Case #%d: %lld\n",h,i*(i+1)/2); else { i--; printf("Case #%d: %lld\n",h,i*(i+1)/2); } } }M.给n行m列座位以及b个坏座位的坐标，单身狗往里面塞，同一排不能挨着，问最多能塞多少人，以及最少塞多少人(能塞的话不能不塞)。 求长度为len的连续空座位最多和最少即可。
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; const int N = 1010; vector<int> vec[N]; void solve(int &p1, int &p2, int d){ p1 += (d+1)/2; while(d > 3){ p2 += 1; d -= 3; } if(d) p2 += 1; } int main(){ int t, cas = 0; scanf("%d", &t); while(t--){ int n, m, p; scanf("%d%d%d", &n, &m, &p); for(int i = 0; i < p; i++){ int x, y; scanf("%d%d", &x, &y); vec[x].push_back(y); } int pre = 0, ans1 = 0, ans2 = 0; for(int i = 0; i < n; i++){ pre = 0; for(int j = 0; j < vec[i].size(); j++){ int dist = vec[i][j] - pre; solve(ans1, ans2, dist); pre = vec[i][j] + 1; } if(pre <= m){ solve(ans1, ans2, m-pre); } vec[i].clear(); } printf("Case #%d: %d %d\n", ++cas, ans1, ans2); } return 0; }L.大矩阵是 给你小矩阵，问是不是大矩阵的一部分。 用两个数定小矩阵在大矩阵的位置，然后验证其他数即可。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long ll; const int N = 1010; ll a[N][N]; ll n, m; ll parselong(char* s){ int len = strlen(s); ll ans = 0; for(int i = 0; i < len; i++){ ans = ans*10+s[i]-'0'; } return ans; } bool check(ll u, ll v, ll x, ll y){ for(ll i = 1; i <= n; i++){ for(ll j = 1; j <= m; j++){ ll x1 = i, y1 = j; ll x2 = x, y2 = y; ll disx = x-i, disy = y-j; if(a[i][j] == -1 && (u-disx)*(v-disy) <= 0) return false; else if(a[i][j] != -1 && a[i][j]!=(u-disx)*(v-disy)) { return false; } } } return true; } vector<pair<ll, ll>> vec; int main(){ int t, cas = 0; scanf("%d", &t); while(t--){ vec.clear(); memset(a, 0, sizeof(a)); scanf("%lld%lld", &n, &m); for(ll i = 1; i <= n; i++){ for(ll j = 1; j <= m; j++){ char s[12]; scanf("%s", s); if(s[0]=='?') a[i][j] = -1; else { a[i][j] = parselong(s); vec.push_back(make_pair(i, j)); } } } //cout << vec.size() << endl; if(vec.size() == 0){ printf("Case #%d: Yes\n", ++cas); } else if(vec.size() == 1){ ll x = vec[0].first; ll y = vec[0].second; int flag = 0; for(ll i = 1; i * i <= a[x][y]; i++){ if(a[x][y] % i == 0){ ll j = a[x][y] / i; if((x<=i && y<=j) || (x<=j && y<=i)){ flag = 1; printf("Case #%d: Yes\n", ++cas); break; } } } if(flag == 0) printf("Case #%d: No\n", ++cas); } else{ ll x1 = vec[0].first, x2 = vec[1].first; ll y1 = vec[0].second, y2 = vec[1].second; ll disx = x2-x1, disy = y2-y1; // cout << x1 << ' ' << y1 << endl; // cout << x2 << ' ' << y2 << endl; // cout << disx << ' ' << disy << endl; int flag = 0; for(ll i = 1; i * i <= a[x2][y2]; i++){ if(a[x2][y2] % i == 0){ ll j = a[x2][y2] / i; if((i-disx)*(j-disy)==a[x1][y1]){ //表示a[x2][y2]是i行j列 flag = 1; if(check(i, j, x2, y2)) printf("Case #%d: Yes\n", ++cas); else printf("Case #%d: No\n", ++cas); break; } else if((j-disx)*(i-disy)==a[x1][y1]){ //表示a[x2][y2]是j行i列 flag = 1; if(check(j, i, x2, y2)) printf("Case #%d: Yes\n", ++cas); else printf("Case #%d: No\n", ++cas); break; } } } if(flag == 0) printf("Case #%d: No\n", ++cas); } } return 0; } /* 10 3 3 4 ? 8 ? 9 ? ? ? ? 3 4 ? ? ? ? ? ? ? ? 3 6 8 12 1 2 1000000000 ? 1 2 ? 1 2 1 ? ? 1 3 ? ? 2 1 3 24 28 36 3 3 ? 5 10 ? 6 12 ? 7 14 2 3 16 18 20 24 27 30 2 3 ? 16 ? ? ? ? */D.给面额A，B两个金额，问最少花多少钱可以让找回来的钱组成B 手算就行。
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int main(){ int t,cas = 0; scanf("%d", &t); while(t--){ double A, B; cin >> A >> B; if(B==0.01) { if(A<0.05) printf("Case #%d: %.2lf\n", ++cas, 0.01); else printf("Case #%d: %.2lf\n", ++cas, 0.02); } else if(B == 0.02) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B == 0.05) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B==0.1) { if(A<0.5) printf("Case #%d: %.2lf\n", ++cas, 0.01); else printf("Case #%d: %.2lf\n", ++cas, 0.02); } else if(B == 0.2) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B == 0.5) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B==1) { if(A<5) printf("Case #%d: %.2lf\n", ++cas, 0.01); else printf("Case #%d: %.2lf\n", ++cas, 0.02); } else if(B == 2) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B == 5) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B==10) { if(A<50) printf("Case #%d: %.2lf\n", ++cas, 0.01); else printf("Case #%d: %.2lf\n", ++cas, 0.02); } else if(B == 20) printf("Case #%d: %.2lf\n", ++cas, 0.01); else if(B == 50) printf("Case #%d: %.2lf\n", ++cas, 0.01); } return 0; }