NOIP 2025 游记
初中 OI 收官之战。
Day -7
上了最后一节常规编程课。
Day -6
依然 whk，虽然 whk 也颓颓颓。
Day -5
领了
Day -4
忘记化学。物理考试最后 10 min 只得了 2 pts。
神秘竞选没选上。
穷到用实验室的吸水纸演算。
Day -3
依然 whk。颓完了。
Day -2
依然 whk。颓了一整天。
Day -1
比赛前一天肚子疼定律成立。
服务区高端厕所，史一样的午饭。
下午去集训，整整 6h 就过了一道橙题。
试机就试了 20 min。我本来是守门员，但是有 2 个用备用机的同学，感动。
Day 1
7:10 起床，左手一直是麻的（一直到晚上也还是麻的）。没睡好，吃饭的时候快睡着了。
到考场也混混欲睡，状态极差。
30 min 写完 T1。测大样例，没过（其实过了），又调了 20 min，但是过程中因查看了调试输出避免了一个问题。大样例全过，但是没写对拍。
1 h 写了 T2 的暴力 20 pts，但是忘了写特殊性质 A。
1.5 h 写了 T3 的暴力 8 pts。
1 h 写了 T4 的 0 pts（读错题了）。
原地 AFO。
Day 6
100 + 20 + 8 + 0 = 128
NOIP 也没赢，甚至比 CSP 还失败。
还是放代码。
::::info[candy]
// 100 pts
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x;
scanf("%lld",&x);
return x;
}
const int N=2e5+10,INF=2e18;
struct node{
int x,y;
}a[N];
struct cdy{
int val,p,id;
friend bool operator<(const cdy cmp1,const cdy cmp2){
return cmp1.val<cmp2.val;
}
friend bool operator>(const cdy cmp1,const cdy cmp2){
return cmp1.val>cmp2.val;
}
};priority_queue<cdy,vector<cdy>,greater<cdy>>pq;
int b[N];
cdy mk_nxt(cdy u){
int p=u.p,id=u.id;
if(id==1){
cdy res={a[p].y,p,2};
return res;
}
cdy res={a[p].x,p,1};
return res;
}
signed main(){
freopen("candy.in","r",stdin);
freopen("candy.out","w",stdout);
int n=read(),m=read();
int minn=INF;
for(int i=1;i<=n;++i){
a[i].x=read(),a[i].y=read();
minn=min(minn,a[i].x+a[i].y);
pq.push({a[i].x,i,1});
}
for(int i=1;i<=n*2;++i){
cdy u=pq.top();pq.pop();
b[i]=b[i-1]+u.val;
pq.push(mk_nxt(u));
}
int ans=0;
for(int i=0;i<=n*2;++i){
if(m-b[i]<0)
break;
ans=max(ans,i+(m-b[i])/minn*2);
}
printf("%lld\n",ans);
return 0;
}
/*
Input #1:
2 10
4 1
3 3
Output #1:
4
Input #2:
3 15
1 7
2 3
3 1
Output #2:
8
My Input #1:
3 11
3 1
1 4
2 3
My Output #1:
6
*/::::
::::info[sale]
// O(T*n^2*2^n) 20pts
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x;
scanf("%lld",&x);
return x;
}
const int N=5e3+10,M=20+10,MOD=998244353;
int n,m,a[N],w[N],dp[M][M];
struct node{
int id,a,w;
friend bool operator<(const node cmp1,const node cmp2){
if(cmp1.a*2/cmp1.w!=cmp2.a*2/cmp2.w)
return cmp1.a*2/cmp1.w>cmp2.a*2/cmp2.w;
if(cmp1.a!=cmp2.a)
return cmp1.a>cmp2.a;
return cmp1.id<cmp2.id;
}
}b[N];
int ans;
bool calc(){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j){
dp[i][j]=dp[i-1][j];
if(j>=w[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+a[i]);
}
for(int i=1;i<=n;++i)
b[i]={i,a[i],w[i]};
sort(b+1,b+n+1);
int sum=0,rest=m;
for(int i=1;i<=n;++i){
if(!rest)
break;
if(rest>=b[i].w){
rest-=b[i].w;
sum+=b[i].a;
}
}
return dp[n][m]==sum;
}
void dfs(int p){
if(p>n){
if(calc())
++ans;
return;
}
w[p]=1;
dfs(p+1);
w[p]=2;
dfs(p+1);
return;
}
void solve(){
n=read(),m=read(),ans=0;
for(int i=1;i<=n;++i)
a[i]=read();
dfs(1);
printf("%lld\n",ans%MOD);
return;
}
signed main(){
freopen("sale.in","r",stdin);
freopen("sale.out","w",stdout);
int c=read(),T=read();
while(T--)
solve();
return 0;
}
/*
Input #1:
0 1
3 2
1 3 5
Output #1：
6
Input #2:
0 1
5 6
122768126 667173684 394970905 333586842 789941810
Output #2:
31
*/::::
::::info[tree]
// O(n^(n+1)) 8pts
#include<bits/stdc++.h>
using namespace std;
int read(){
int x;
scanf("%d",&x);
return x;
}
const int N=8e3+10;
vector<int>vc[N],ls[N];
int n,m,a[N],ans,cnt,siz[N];
int calc(vector<int>vec){
int len=vec.size();
for(int i=0;i<len;++i)
if(vec[i]!=i)
return i;
return len;
}
void merge_vec(vector<int>&vc1,const vector<int>vc2){
int l1=vc1.size(),l2=vc2.size();
vector<int>res;
int i=0,j=0;
while(i<l1&&j<l2){
if(vc1[i]<vc2[j]){
res.push_back(vc1[i]);
++i;
}
else{
res.push_back(vc2[j]);
++j;
}
}
while(i<l1){
res.push_back(vc1[i]);
++i;
}
while(j<l2){
res.push_back(vc2[j]);
++j;
}
res.erase(unique(res.begin(),res.end()),res.end());
vc1=res;
return;
}
void dfs(int u){
ls[u].push_back(a[u]);
for(auto v:vc[u]){
dfs(v);
merge_vec(ls[u],ls[v]);
}
cnt+=calc(ls[u]);
return;
}
void _dfs(int p){
if(p>n){
cnt=0;
for(int i=1;i<=n;++i)
ls[i].clear();
dfs(1);
ans=max(ans,cnt);
return;
}
for(int i=0;i<n;++i){
a[p]=i;
_dfs(p+1);
}
return;
}
long long pianfen_ans,pianfen_cnt;
void pianfen(int u){
ls[u].push_back(pianfen_cnt);
++pianfen_cnt;
for(auto v:vc[u]){
dfs(v);
merge_vec(ls[u],ls[v]);
}
pianfen_ans+=calc(ls[u]);
return;
}
void solve(){
n=read(),m=read();
for(int i=1;i<=n;++i)
vc[i].clear();
for(int i=2;i<=n;++i){
int fa=read();
vc[fa].push_back(i);
}
if(n<=7){
ans=0;
_dfs(1);
printf("%d\n",ans);
return;
}
// Ӧ DP
// Ȱ Ȩֵ ÿ
pianfen_ans=0,pianfen_cnt=0;
for(int i=1;i<=n;++i)
ls[i].clear();
pianfen(1);
printf("%lld\n",pianfen_ans);
return;
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int T=read();
while(T--)
solve();
return 0;
}
/*
Input #1:
2
5 2
1 1 2 2
7 2
1 1 2 2 2 3
Output #1:
9
13
My Input #1:
1
4 2
1 2 2
My Output #2:
8
*/::::
::::info[query]
// 写了 1h 一分没拿到
// 0 pts
#include<bits/stdc++.h>
using namespace std;
int read(){
int x;
scanf("%d",&x);
return x;
}
const int N=3e3+10;
int a[N];
unsigned long long p[N],ans[N];
//struct node{
// int L,R;
//};vector<node>queries;
struct segtr{
int l,r;
unsigned long long val;
}tr[N*4];
void pushup(int u){
tr[u].val=max(tr[u*2].val,tr[u*2+1].val);
return;
}
void build(int u,int l,int r){
tr[u].l=l,tr[u].r=r;
if(l==r){
tr[u].val=(unsigned long long)a[l];
return;
}
int mid=(l+r)>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
pushup(u);
return;
}
unsigned long long query(int u,int l,int r){
if(l<=tr[u].l&&r>=tr[u].r)
return tr[u].val;
int mid=(tr[u].l+tr[u].r)>>1;
unsigned long long res=0;
if(l<=mid)
res=query(u*2,l,r);
if(r>mid)
res=max(res,query(u*2+1,l,r));
return res;
}
int main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
int n=read();
for(int i=1;i<=n;++i){
a[i]=read();
p[i]=p[i-1]+a[i];
}
build(1,1,n);
int Q=read(); //,maxLR=0,maxR=0;
while(Q--){
int L=read(),R=read();
for(int i=1;i<=n;++i)
ans[i]=0;
for(int i=1;i<=n;++i)
for(int len=L;len<=R;++len)
ans[i]+=query(1,max(0,i-len+1),min(n,i+len-1));
unsigned long long res=0;
for(int i=1;i<=n;++i)
res^=ans[i]*i;
printf("%llu\n",res);
// queries.push_back({L,R});
// maxLR=max(maxLR,R-L+1);
// maxR=max(maxR,R);
}
// if(n<=3000){
// vector<vector<unsigned long long>>cnt(n+5,vector<unsigned long long>(n+5,0));
// // cnt[len][i]: 长度为 len 包含 i 的
// for(int i=1;i<=n;++i)
// for(int j=i;j<=n;++j){
// unsigned long long sum=p[j]-p[i-1];
// for(int k=i;k<=j;++k)
// cnt[j-i+1][k]=max(cnt[j-i+1][k],sum);
// }
// for(auto q:queries){
// int L=q.L,R=q.R;
// vector<unsigned long long>ans(n+5,0);
// for(int len=L;len<=R;++len)
// for(int i=1;i<=n;++i)
// ans[i]+=cnt[len][i];
// unsigned long long res=0;
// for(unsigned long long i=1;i<=n;++i)
// res^=i*ans[i];
// printf("%lld\n",res);
// }
// return 0;
// }
// if(maxLR==1){
//
// return 0;
// }
// if(maxR<=32){
//
// return 0;
// }
return 0;
}
/*
Input #1:
4
2 4 5 1
3
1 2
3 4
1 4
Output #1:
18446744073709551603
8
4
*/ ::::
Day 14
2=，