ICPC 新疆省赛2026
传送门
赛时开出来的
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");
}
}
else
puts("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]; // 如果不存在则默认为 0
ans[ev.qid] += ev.delta * cur_cnt;
}
}
for (int x : ans) cout << x << '\n';
}
return 0;
}
赛时应该大部分都是字典树，可持久化字典树这种做法，我提供一个思路
奖牌
依然铜奖，喜提雷蛇鼠标
浙公网安备 33010602011771号