每次打比赛都能有一些收获，这次主要有以下几个点：
最早在看《算法竞赛入门到进阶》的时候看到了《代码规范》，我觉得很多都很好，因为这样规范不只可以让代码更统一，很多的细节的地方更可以避免不必要的问题，但是有一个点我当时不是很明白，就是“变量定义”，他建议变量在离使用最近的地方定义，我主要有两个点比较疑惑：1.把一些变量和数组定义成全局变量可以少写很多函数参数，方便很多；2.游标值有的时候可以再利用。
这次打比赛就出现了这个问题，我把游标变量i定义成的全局变量，导致我看了很久都没发现居然是这个问题错了……总之就是代码规范是长期实践总结出来的经验，按照代码规范来写可以有效地避免没有想到的bug。
然后这次比赛的A题是用python过的，需要再花时间掌握分步取模（也就是CZL说的拆解）。
寒假的前半段时间主要花在了啃一些硬骨头上面，可能确实比他们慢一些，但是这样至少扎实一些，我觉得是值得的。所以我其实没有掌握太多，目前做位运算的练习稍多一些，本来想在比赛前看看并查集的，但是完全来不及了，临时补了一下矩阵快速幂也没用上。（此处感谢青竹大佬的帮助
另外这次比赛一个明显的问题就是cin/cout不敢用 因为慢。而且我G题本来TLE，加了这句话
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
以后直接RE了，不知道为什么
G题
https://ac.nowcoder.com/acm/contest/3002/G
其实算是我这次比赛的遗憾了，过的人数比我的排名高……
我当时的实现想法就是一个从k到n逐渐变大的滑块，不断检索。O(N^2)，但是实际上会小一些，差不多是O(N^1.5)?
估计ZT他们也是差不多的思路，反正就是TLE了。
其实打字打到这里我就有了一些更多的想法，比如 检索到了就直接return 不应该单独逐次统计，这样的话每一个二级循环对应的是大约30个语句，如果实现了这个优化可能可以让二级循环每个对应的语句减少80%。
啊……我比赛的时候怎么没想到。
其实和下面的思路在实现上是差不多的：就是一边进元素一边查。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
string str;
map<char,int> mp;
int main(){
cin>>n>>k>>str;
int ans=-1,l=0,cnt=0;
for(int i=0;i<n;i++){
char c=str[i];
mp[c]++;
while(mp[c]==k){
if(ans==-1) ans=i-l+1;
else ans=min(ans,i-l+1);
mp[str[l]]--;
l++;
}
}
printf("%d\n", ans);
return 0;
}其实根本没用到map，时间上也不是很优秀——但就是这样本菜鸡都没想到。
它的实现逻辑就是从前往后找，找到了以后再删前面的，最后头尾减一下就是了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
char s[maxn];
vector<int> g[26];//26个容器
int main() {
int n,k;
cin>>n>>k>>s;
for(int i=0; i<n; i++)
g[s[i]-'a'].push_back(i);//统计整个字串的字母及其出现的位置
int ans=n+1;
for(int i=0; i<26; i++)
if(g[i].size()>=k)
for(int j=k-1; j<g[i].size(); j++)
ans=min(ans,g[i][j]-g[i][j-k+1]+1);//比最小
if(ans!=n+1) cout<<ans<<endl;
else puts("-1\n");
}这个容器的写法也很漂亮。复杂度是O(n)，语句数量差不多是4n左右。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
typedef long long ll;
char s[maxn];
int n, k, p[30];
bool check(int x) {
memset(p, 0, sizeof(p));
for (int i = 1; i <= x; i++) {//这个是从原始字串的左端开始 长度为x
p[s[i] - 'a']++;
if(p[s[i] - 'a'] >= k) return true;//边进边查 查到返回
}
for (int i = x + 1; i <= n; i++) {//第二个指针
//上次没有搜到的部分 如果程序走到了这里，就说明头x个字母不满足
p[s[i] - 'a']++;//选取
p[s[i-x] - 'a']--;//丢弃
if(p[s[i] - 'a'] >= k) return true;
}
return false;
}
int main() {
cin >> n >> k;
scanf("%s",s +1);
int left = 1, right = n, ans = -1;
while (left <= right) {
int mid = left+((right-left)>>1);//这种写法比青竹大佬的写法更好
if(check(mid)) {
ans = mid;
right = mid - 1;
} else left = mid + 1;
}
printf("%d\n", ans);
return 0;
}青竹大佬的二分写法真的亮到我了。
我最先看的就是这个写法，首先在外层的长度选取上使用二分，然后在内层的已知长度求是否满足的函数里使用双指针，这样就是一个O(nlogn)的复杂度。
啊 我为什么没想到。
三月回来重做G题，wa了，忽视了多个满足k的情况的比较（也忘记了可以用双指针。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int main() {
int n, k;
string s;
cin >> n >> k >> s;
map<char, int> mp;
int ans = -1;
for (int R = 0, L = 0; R < n; ++R) {
++mp[s[R]];
if (mp[s[R]] == k) {
for (; L < R; L++) {
if (s[L] == s[R]) break;
--mp[s[L]];
}
if (ans == -1)
ans = R - L + 1;
else
ans = min(ans, R - L + 1);
--mp[s[L++]];//释放最左侧的位点，才能进行下一轮比较
}
}
cout<<ans<<endl;
return 0;
}H题
https://ac.nowcoder.com/acm/contest/3002/H
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int main() {
int n, k;
string s;
cin>>n>>k>>s;
map<bool,int>cnt;
int ans=-1;
for(int i=0,l=0;i<n;++i){
++cnt[s[i]-'0'];
while(min(cnt[0],cnt[1])==k){
char M;
if(cnt[0]>cnt[1])M='0';
else M='1';
int j=i+1;
for(;s[j]==M&&j<n;++j) ;
ans=max(j-l,ans);
--cnt[s[l++]-'0'];
}
}
if(ans==-1) cout<<n<<endl;
else cout<<ans<<endl;
return 0;
}这个完全是我自己想出来的，其实和G很像，wa了两次才想出来要加一个后缀搜索
京公网安备 11010502036488号