传送门
赛时开出来的
C: Size Comparison
糖丸了模拟题，要求输出Bigger，输出了larger，吃了罚时
点击查看代码
#include<bits/stdc++.h>
using namespace std;using ll=long long ;
const int maxn=2e5+10;using pii=pair<int,int>;
map<char,int>mp;
void solve(){string x,y;cin>>x>>y;int numx=0,lenx=x.length();int numy=0,leny=y.length();bool book=0;for(auto c:x){if(c=='X' && x[0]=='X' ){numx++;}else if(c>='0' && c<='9'){numx=numx*10+(c-'0');}}for(auto c:y){if(c=='X' && y[0]=='X'){numy++;}else if(c>='0' && c<='9'){numy=numy*10+(c-'0');}}//cout<<numx<<" "<<numy<<endl;if(x[lenx-1]==y[leny-1]){if(numx==numy){puts("Equal");}else{char s=x[lenx-1];if(s=='L'){if(numx>numy){puts("Bigger");}else if(numx<numy){puts("Smaller");}else puts("Equal");}else{if(numx<numy){puts("Bigger");}else if(numx>numy){puts("Smaller");}else puts("Equal");}}}else{if(x[lenx-1]=='L'){puts("Bigger");}else if(x[lenx-1]=='M'){if(y[leny-1]!='S'){puts("Smaller");}else{puts("Bigger");}}elseputs("Smaller");}}int main(){int _;cin>>_;while(_--){solve();} return 0;
}F: Climbing Taihang Mountains in Snow
一眼秒出思路，经典前缀和，一发入魂
点击查看代码
#include<bits/stdc++.h>
using namespace std;using ll=long long ;
const int maxn=2e5+10;
#define x first
#define y second
using pii=pair<int,int>;
int n;
// const int maxn=2e5+10;
struct node{int h,a,b;
}e[maxn];
ll prea[maxn],preb[maxn];
bool cmp(node a,node b){return a.h<b.h;
}
void solve(){cin>>n;for(int i=1;i<=n;++i)cin>>e[i].h;for(int i=1;i<=n;++i)cin>>e[i].a;for(int i=1;i<=n;++i)cin>>e[i].b;sort(e+1,e+1+n,cmp);ll sumn=0;for(int i=1;i<=n;++i){prea[i]=prea[i-1]+e[i].a;preb[i]=preb[i-1]+e[i].b;}ll ans=0;for(int i=0;i<=n;++i){ans=max(ans,prea[i]+preb[n]-preb[i]);}cout<<ans<<endl;return ;
}int main(){int _;
// cin>>_;_=1;while(_--){solve();} return 0;
}G: Tidying the Row
在I wa了3发之后，0基础队友发现了他觉得很简单的题，甚至讲出了完整思路，然后直接秒了
点击查看代码
#include<bits/stdc++.h>
using namespace std;using ll=long long ;
const int maxn=2e5+10;
#define x first
#define t second
ll n;
map<int,vector<int>>mp;
void solve(){cin>>n;for(int i=1;i<=n;++i){int x;cin>>x;mp[x].push_back(i);}ll num;ll ans=1e9;vector<int>cnt;for(auto [c,a]:mp){if(a.size()>cnt.size()){cnt=a;num=c;}}for(auto [c,a]:mp){if(a.size()==cnt.size()){
// cout<<c<<endl;ll l1=a[0],l2=a[0],r1=a[a.size()-1],r2=a[a.size()-1];for(int i=0;i<a.size();++i){if(a[i]==a[i+1]-1){l1=a[i+1]; }else break;}for(int i=a.size()-1;i>0;--i){if(a[i]==a[i-1]+1){r2=a[i-1]; }else break;}
// cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;ans=min(ans,min(r2-l2,r1-l1));}}cout<<ans<<endl;return ;
}int main(){int _;
// cin>>_;_=1;while(_--){solve();} return 0;
}
I:Elemental Monuments
老实说也是一眼出思路的题，可惜因为没看到数据范围，没看到数据还能是负数wa了好几回
这个时候另一个队友造了极大的数据，发现了要用long long
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long ;
const int maxn=2e5+10;#define x first
#define t second
using pii=pair<int,int>;
int n;
// const int maxn=2e5+10;
pii e[maxn];
ll pre[maxn][2];
int s;
int ef(pii x){int l=0,r=n+1;ll p=x.x;while(l<=r){int mid=(l+r)>>1;if(e[mid].x<=p){l=mid+1;}else{r=mid-1;}}return l;
}
void solve(){cin>>n>>s;e[0]={-1e10-1,0};e[n+1]={1e10+1,1};for(int i=1;i<=n;++i)cin>>e[i].x;for(int i=1;i<=n;++i){cin>>e[i].t;pre[i][0]=pre[i-1][0];pre[i][1]=pre[i-1][1];if(e[i].t!=0) continue;if(abs(e[i].x)%2){pre[i][1]++;
// cout<<"odd";}else pre[i][0]++;}
// for(int i=1;i<=n;++i){
// cout<<e[i].x<<" ";
// }cout<<endl;
// for(int i=1;i<=n;++i){
// cout<<e[i].t<<" ";
// }// for(int i=1;i<=n;++i){
// cout<<pre[i][0]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n;++i){
// cout<<pre[i][1]<<" ";
// }
// cout<<endl;ll ans=0;for(int i=1;i<=n;++i){int t=e[i].t;if(t==1){int l,r;l=ef({e[i].x-2*s,0});r=ef({e[i].x+2*s,0});l=max(l,0ll);r=min(r,n+1);while(e[i].x-2*s>=e[l].x && l<=n) ++l;while(e[i].x+2*s<=e[r].x && r>=1) --r ;//cout<<l<<" "<<r<<endl;if(abs(e[i].x)%2){ans+=pre[r][1]-pre[max(0ll,l-1)][1];}else ans+=pre[r][0]-pre[max(0ll,l-1)][0];//cout<<ans<<endl;}}cout<<ans<<endl;}signed main(){int _;
// cin>>_;_=1;while(_--){solve();} return 0;
}赛时没开出来的
D：Longest Common Prefix：
挺板的题，因为队友带的板子不全，甚至有书只讲算法不给代码，太神秘了
当时想到了字典树，可惜没板子，而且也不会处理这种区间内的，不过到了最后结束时，注意到可以用离线的做法，随让AI做了一个
点击查看代码
#include <bits/stdc++.h>
using namespace std;using ull = unsigned long long;
const ull base = 131; // 大于3的基数struct Event {int qid; // 查询编号int delta; // +1 或 -1，表示对答案的增幅ull h; // 需要观察的前缀哈希
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {int n, q;cin >> n >> q;vector<string> s(n + 1);for (int i = 1; i <= n; ++i) cin >> s[i];vector<int> ans(q, 0);vector<vector<Event>> events(n + 2); for (int qid = 0; qid < q; ++qid) {int l, r;string t;cin >> l >> r >> t;ull h = 0;for (char c : t) {h = h * base + (c - '0' + 1);events[l - 1].push_back({qid, -1, h});events[r].push_back({qid, +1, h});}}unordered_map<ull, int> cnt; // 当前拥有某前缀的字符串个for (int i = 1; i <= n; ++i) {ull h = 0;for (char c : s[i]) {h = h * base + (c - '0' + 1);cnt[h]++;}for (auto &ev : events[i]) {int cur_cnt = cnt[ev.h]; // 如果不存在则默认为 0ans[ev.qid] += ev.delta * cur_cnt;}}for (int x : ans) cout << x << '\n';}return 0;
}
赛时应该大部分都是字典树，可持久化字典树这种做法，我提供一个思路
奖牌
依然铜奖，喜提雷蛇鼠标