感觉还好，签到没有用到什么难的算法，水过几道签到题就挂机，贼拉爽哈哈哈
A题
逆向思维，假设所有的纸币加起来总共有sum元，s张，sum减去n元记为x元，
把x用尽量少的ss张纸币表示出来，ans = s - ss
注意：不能直接贪心，假设x = 60元，有50元纸币1张，20元纸币3张，显然不能直接用50元的，那怎么办呢？ 搜索啊
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<set> #include<bitset> #include<vector> using namespace std; const int INF = 0x3f3f3f3f; int T,sum,ans,ss,n; int a[11],b[11] = {0,1,5,10,20,50,100,200,500,1000,2000}; void dfs(int sum,int t,int s) { if(sum == 0) { ss = min(s,ss); return; } if(sum < 0 || t < 1) return; int k = min(sum / b[t],a[t]); dfs(sum - k * b[t],t - 1,s + k); if(k > 0) dfs(sum - (k - 1) * b[t],t - 1,s + k - 1); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); ans = sum = 0; for(int i = 1;i <= 10; ++i) { scanf("%d",&a[i]); ans += a[i]; sum += a[i] * b[i]; } sum -= n; ss = INF; dfs(sum,10,0); if(ss == INF) printf("-1\n"); else printf("%d\n",ans - ss); } return 0; }F题
这个题刚开始想简单了，直接看了大小关系改变小于等于1次的就是合法的
结果还没等交就出了组样例卡住了 1 2 7 1 3 4 5
所以就想怎么办呢？
记录相邻两个数的大小关系出现次数
记录隔一个数字的两个数的大小关系出现次数
如果大于等于（或小于等于）的出现次数满足>=正常的有序数列中的数字-1即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<set> #include<bitset> #include<vector> using namespace std; int a[100010]; int T,n; int x1,x2,x3,y1,y2,y3; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int flag = 0; x1 = x2 = x3 = y1 = y2 = y3 = 0; for(int i = 1;i <= n; ++i) scanf("%d",&a[i]); for(int i = 1;i < n; ++i) { if(a[i] > a[i + 1]) x1++; if(a[i] < a[i + 1]) x2++; if(a[i] == a[i + 1]) x3++; } for(int i = 1;i < n - 1; ++i) { if(a[i] > a[i + 2]) y1++; if(a[i] < a[i + 2]) y2++; if(a[i] == a[i + 2]) y3++; } if(x1 + x3 >= n - 2 && y1 + y3 >= n - 3) flag = 1; if(x2 + x3 >= n - 2 && y2 + y3 >= n - 3) flag = 1; if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }G题
给出n个点坐标问是否是正多边形
对正多边形不是很了解所以想了一会，其实判断正多边形只需要看边长相等即可
我没有想到这个，直接想，正多边形任意两点之间能构成的线段长度有多少种 n/2，扔到set里去个重即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<set> #include<bitset> #include<vector> using namespace std; set<int>q; int T,x[110],y[110],n; int jl(int k,int l) { return (x[k] - x[l]) * (x[k] - x[l]) + (y[k] - y[l]) * (y[k] - y[l]); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); q.clear(); for(int i = 1;i <= n; ++i) { scanf("%d%d",&x[i],&y[i]); for(int j = 1;j < i; ++j) q.insert(jl(i,j)); } if(q.size() == n / 2) printf("YES\n"); else printf("NO\n"); } return 0; }H题
刚开始没看懂题
树上每个节点有一个清凉度，清凉度是一个关于节点度的函数 问能够组成树的最大清凉度是多少
后来想一颗n个点的树所有的度是2n-2，其中每个点的度>=1,所以只需要分配剩下的n-2个度就可以了
（有初始限定的完全背包）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<set> #include<bitset> #include<vector> using namespace std; int f[2200],a[2200]; int T,n,ans; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i = 0;i < n - 1; ++i) { scanf("%d",&a[i]); if(i) a[i] -= a[0]; } for(int i = 0;i <= n; ++i) f[i] = -0x3f3f3f3f; f[0] = a[0] * n; for(int i = 1;i < n; ++i) for(int j = i;j <= n - 2; ++j) f[j] = max(f[j],f[j - i] + a[i]); printf("%d\n",f[n - 2]); } return 0; }J题
eennn，这个题好坑，9s的时限，我不敢跑暴力一直拦着队友，后来发现他喵的暴力还真能过
正解是01字典树（有空看去吧）
L题
模拟，求一个不规则图形的表面积（除底面）
直接模拟就好
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<set> #include<bitset> #include<vector> using namespace std; int T,n,m; int ans,a[60][60]; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); ans = 0; for(int i = 1;i <= n; ++i) for(int j = 1;j <= m; ++j) { scanf("%d",&a[i][j]); if(a[i][j]) ans++; } for(int i = n; i > 1; --i) for(int j = 1;j <= m; ++j) ans += abs(a[i][j] - a[i - 1][j]); for(int j = 2;j <= m; ++j) for(int i = 1;i <= n; ++i) ans += abs(a[i][j] - a[i][j - 1]); for(int i = 1;i <= n; ++i) ans += a[i][1] + a[i][m]; for(int j = 1;j <= m; ++j) ans += a[1][j] + a[n][j]; printf("%d\n",ans); } return 0; }
