今天水了一节英语课，翘了一节C++课，就是感觉摆的一批。
对局匹配
P8656 [蓝桥杯 2017 国 B] 对局匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
对于这道题：
大佬解法1：
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, k, a[N], ans, cnt[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; cnt[a[i]]++; } if(k == 0) { for(int i = 0; i <= 100000; i++) if(cnt[i]) ans++; cout << ans; return 0; } for(int i = 0; i <= 100000 - k; i++) { if(cnt[i] < cnt[i + k]) cnt[i + k] -= cnt[i]; else cnt[i + k] = 0; } for(int i = 0; i <= 100000 - k; i++) ans += cnt[i]; cout << ans; return 0; }
好像是用了什么桶之类的东西，不过目前我还没学过，先不管
就是假如k=1, a[2]=3(3个人),a[3]=4(4个人),a[5]=1(1个人)
那么，积分为2和积分为3的人可以匹配，因为匹配是两个人嘛，所以噶掉其中一个，保留另一半，此时a[3]=4-3=1，然后到了后面算a[4]的时候，因为我们每次噶掉的是后面的人，所以保证了前面的都算过而且下一次算后面的人的时候不会有重复或者遗漏（也就是说，我每次算的时候统一让他保留小的，达成一致，这样就不会出问题），有一种1+1=0的感觉。
dp方法：
有一说一这道题的标签是dp，但是我死活想不出来它的状态转移方程（因为我还是一只蒟蒻），所以copy了佬的题解
下面是代码：
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const int mod = 1e9 + 7; inline int read() { int x(0),f(0); char ch=getchar(); for(; !isdigit(ch); ch=getchar()) f|=(ch=='-'); for(; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); return f?-x:x; } int n,k,ans; int a[N],d[N],g[N]; int dp[N][2]; vector<int> v[N]; int main() { n=read(), k=read(); for(int i = 1; i <= n; i++) a[i]=read(),d[a[i]]++;; sort(a+1, a+n+1); int m = unique(a+1, a+n+1)-a-1; if(k == 0) { printf("%d\n", m); return 0; } for(int i = 1; i <= m; i++) { g[a[i]]++; if(g[a[i]] == 1) v[a[i] % k].push_back(i); } // dp for(int i = 0; i < k; i++) { if(v[i].empty()) continue; int siz = v[i].size(); memset(dp, 0x3f, (siz + 5) * sizeof(dp[0][0])); for(int j = 0; j < siz; j++) { if(j == 0) dp[0][1] = d[a[v[i][j]]], dp[0][0] = 0; else if((a[v[i][j]] - a[v[i][j-1]]) == k) { dp[j][0] = max(dp[j-1][1], dp[j-1][0]); dp[j][1] = dp[j-1][0] + d[a[v[i][j]]]; } else { dp[j][0] = max(dp[j-1][1], dp[j-1][0]); dp[j][1] = max(dp[j-1][1], dp[j-1][0]) + d[a[v[i][j]]]; } } ans += max({dp[siz - 1][0], dp[siz - 1][1]}); } printf("%d\n",ans); }
。。。。。。
砝码称重
P2347 [NOIP1996 提高组] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我fu了，我是sb好吧
典：背包题，属于能否/判断的背包，能否到达型，下面是题解
#include<iostream> using namespace std; const int N=1005; int m[N],a[7]; int ans=0,maxn=0; void solution(int a[]) { for(int i=1;i<=6;i++) //第i种砝码 { int l; if(i==4)l=5; else if(i==5)l=10; else if(i==6)l=20; else l=i; //l是重量 for(int j=0;j<a[i];j++) //放j个的情况 { for(int k=N-l;k>=0;k--) if(m[k])m[k+l]=1; } } for(int i=0;i<N;i++)if(m[i])ans++; ans--; } int main() { m[0]=1; for(int i=1;i<=6;i++)cin>>a[i]; solution(a); cout<<"Total="<<ans; system("pause"); return 0; }
核心就是判断重量x是否成立，如果成立，那么重量x+k也成立
这道题数据太水了，以至于我看到有人说六个循环都能过，六个循环就是枚举，我甚至看到有人用二进制优化（bushi）来讽刺这道题的水数据，我写的巨拉，建议跳过不要看
下面是佬的题解：
佬：我们用一个bitset保存每个重量能否被称出即可。
#include <bitset> #include <cstdio> int a[10], w[10] = {1, 2, 3, 5, 10, 20}; std::bitset<1010> S; int main() { for(int i = 0; i < 6; i++) scanf("%d", a + i); S[0] = 1; for(int i = 0; i < 6; i++) for(int j = 0; j < a[i]; j++) S |= S << w[i]; printf("Total=%d\n", S.count() - 1); return 0; }
。。。。。。
单词接龙
P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我不会，无法从我的大脑里面搜索到相关内容，但是我觉得有必要学习
佬：
C++ #include<bits/stdc++.h> using namespace std; string str[20]; int use[20], length = 0, n; int canlink(string str1, string str2) { for(int i = 1; i < min(str1.length(), str2.length()); i++) {//重叠长度从1开始，直到最短的字符串长度-1（因为不能包含） int flag = 1; for(int j = 0; j < i; j++) if(str1[str1.length() - i + j] != str2[j]) flag = 0;//逐个检测是否相等 if(flag) return i;//检测完毕相等则立即return } return 0;//无重叠部分，返回0 } void solve(string strnow, int lengthnow) { length = max(lengthnow, length);//更新最大长度 for(int i = 0; i < n; i++) { if(use[i] >= 2) continue;//该字符串使用次数需要小于2 int c = canlink(strnow, str[i]);//获取重叠长度 if(c > 0) {//有重叠部分就开始dfs use[i]++; solve(str[i], lengthnow + str[i].length() - c); use[i]--; } } } main() { cin >> n; for(int i = 0; i <= n; i++) use[i] = 0, cin >> str[i];//str[n]为开始字符 solve(' '+str[n], 1);//有必要解释一下开始阶段。为了指定第一个字符，而且因为canlink需要重叠部分小于最短长度-1，所以要从前面添加一个无意义充长度的‘ ’。这样就强制了canlink函数比较最后一位。 cout << length ; }
好，点到为止。