NOIP 2025 邮寄

· · 生活·游记

Day -15 \sim -3

-S 擦线蓝勾耶耶耶耶耶。@stem12345xi 5级你就受着 /kel

畜中生体验卡，去玩玩叭。

写了一些 dp 和思维题。

后期开始复习那些忘了的板子：快速幂；最小生成树；tarjan 一家子；拓扑；floyd；其它都不会啦啦啦哇哇哇

Day -2

写一些绿的板子加强 1.. 的题，幻想能过掉 NOIP T1。

开摆。

必赢的！输了就受着呗

整理所有板子。追忆之前写题记录下来的思维，泪目。

Day -1

板子搞定！dp 搞定！

晚上吃之前吃的。本来想把碗里的蒜舀出来然后把蒜全溶汤里了呜呜呜呜

买了瓶水溶 C 考场上喝。

洗澡。洗发露不好闻但是效果不错111。

Day 1

吃饭。茶叶蛋+黄桃+白米粥。疑似着凉了肚子疼了 15min。带了 ( 水溶 C + 巧克力 )\times 3。

我爸说步行 10min 到考场，然后走了15min发现是开车 10min。紧急打车。

8:16 进考场，竟然是 win10。

吃喝吃喝。

T1 1.5h 干完主要是贪心一堆不对的地方改了老半天才过掉。吃喝吃喝。

T2 什，好像是 dp。写了个特殊性质 A 走了。吃喝吃喝。

T3 什么树形 dp，推了好久然后一写样例不过气死了。吃喝吃喝。

T4 O(n^3q)。彳亍。吃喝吃喝。中午吃不下饭了。

考试结束前 15min：啊？T2 还有 m=2 的数据？然后 15min 没想出来。受着了！！！ 出考场一直在骂。

黄紫黑黑你当 noi 呢，早知道不想 T3T4 了。炸了。如果能上 100 已经可以了 /ll。

初二还有机会叭。如果 T1 真的过了就是 2= 叭。

和 @stem12345xi 一起走的，中午巧克力吃饱了没吃饭（？），去沙滩上放松了会，聊了会奇怪的东西。@stem12345xi 踢了一脚的沙子，在沙滩上写了个大大的 FKCCF，并由他妈拍照留念。禁三警告。

体验就当是玩叭。地铁上玩 phi + 打牌。

Day 2

回家后做出来了 T2 m=2 20pts 数据和 T4 O(n^3+qn^2) 的时间复杂度。早知道不肝 T3 了你连个 dp 都不会做你还想做黑树形 dp 你真是xxxx

Day 5

90+4+0+5=99pts。《如果能上 100 已经可以了》好了没上。

考场代码放送。

::::info[T1]

/*
Wow! It's Win 10! 

8:37 have T1's thought.
it's like tanxin.

8:55 done. yangli buguo.

9:02 test1235 ac. test467 wa.
in all wa test, i cout something smaller than std. Nanana.

9:40 test7 ac! test6 wa.
my ans = std - 1.
maybe ill check T2 first.

12:25 back to debug.

12:35 find the bug!

12:39 all past!
*/

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e5+5;
int n,m,ansm,ansn;
struct xy
{
    int x,y,sum;
}a[N];
int vis[N];

signed main()
{
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
      scanf("%lld%lld",&a[i].x,&a[i].y),a[i].sum=a[i].x+a[i].y;
    sort(a+1,a+n+1,[](xy x,xy y) {return x.x<y.x;});
    int mins=LLONG_MAX,ix=0;
    for(int i=1;i<=n;i++)
        if(a[i].sum<mins)
        {
            mins=a[i].sum;
            ix=i;
        }
    int total=0,tt=0,cnt=0,temp=0;
    bool flag=1;
    for(int i=1;i<=n;i++)
    {
        if(i==ix)
          continue;
        total+=a[i].x;
        tt+=a[i].x;
        cnt++;
        if(cnt%2==0)
        {
            if(tt<mins)
            {
                if(total>m)
                {
                    flag=0;
                    break;
                }
                ansm=total;
                ansn+=2;
                tt=0;
            }
            else
              break;
        }
        if(cnt%2==1)
          temp=i;
    }
    int dif=m-ansm;
    ansm+=((dif/mins)*mins);
    ansn+=((dif/mins)*2);
    int minn=LLONG_MAX,maxn=-1;
    if(flag)
    {
        minn=min(a[temp].x,a[ix].x);
        maxn=max(a[temp].x,a[ix].x);
        if(minn<=m-ansm)
          ansm+=minn,ansn++;
        if(maxn<=m-ansm)
          ansm+=minn,ansn++;
    }
    else
    {
        minn=a[ix].x;
        if(minn<=m-ansm)
          ansm+=minn,ansn++;
    }
    int lst=0;
    if(temp-1==ix)
      lst=temp-2;
    else
      lst=temp-1;
    dif=m-ansm;
    if(dif+a[lst].x>=mins)
      ansn++;
    return !printf("%lld\n",ansn);
}

:::: ::::info[T2]

/*
9:40 subA is so simple! but just 4 pts. sad.

12:50 i have a little thought about m=2 sub.
but i have no time.

12:55 i probably know how to do that sub. wuwuwu.
*/

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=5005,M=1e4+5,mod=998244353;
int t,n,m,a[N];

int pow2()
{
    int x=2,y=n,res=1;
    while(y>0)
    {
        if(y&1)
          res=(res*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}

signed main()
{
    freopen("sale.in","r",stdin);
    freopen("sale.out","w",stdout);
    scanf("%lld",&t);
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        bool is_subA=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            if(i!=1 && a[i]!=a[i-1])
              is_subA=0;
        }
        if(is_subA) // pls give me 4 pts!
        {
            printf("%lld\n",pow2());
            continue;
        }
        puts("0"); // No. sir.
    }
    return (0.0);
}

:::: ::::info[T3]

/*
10:05 first happily build the tree.

10:15 have some simple ideas.

10:52 i think im really close to the right si lu
but i think my dp has some tanxin problems.
its soooooooo disgusting.
its like O(2^son). but if so, idk how to write a absolutly correct dp.
my brain is like boom boom boom. >_<

10:55 if i write a extreme code, can sisief give me some pts qwq.

11:16 write 1/2 code and then don't know how to write. 0pts then.
maybe i can think about the m<=2. yebuhui zenmeban.

11:22 i give up. go to T4. maybe this is a blue or purple problem. hard enough.
*/

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define clr(x,y) memset(x,y,sizeof x)

const int N=8005,M=805;
int t,n,pre[N],cur,dep[N],dp[N][2],maxdep;
struct edge
{
    int l,r,nxt;
}e[M*2];

void ae(int u,int v) {e[++cur]={u,v,pre[u]},pre[u]=cur;}

void get_dep(int x,int f)
{
    dep[x]=dep[f]+1;
    for(int i=pre[x];i;i=e[i].nxt)
    {
        int r=e[i].r;
        if(r==f)
          continue;
        get_dep(r,x);
    }
}

int cnt=0;

void dfs(int x,int f)
{
    bool flag=0;
    for(int i=pre[x];i;i=e[i].nxt)
    {
        int r=e[i].r;
        if(r==f)
          continue;
        dfs(r,x);
        flag=1;
        dp[x][0]+=dp[r][0];
        dp[x][1]+=dp[r][1];
    }
    if(!flag)
    {
        dp[x][1]=(cnt==0)?1:0;
        dp[x][0]=1;
    }
    else
    {
        dp[x][1]+=(cnt+1);
        dp[x][0]+=(maxdep-dep[x]+1);
    }
    cnt++;
}

signed main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%lld",&t);
    while(t--)
    {
        clr(e,0),clr(pre,0),cur=0;
        scanf("%lld",&n);
        for(int i=2,x;i<=n;i++)
          scanf("%lld",&x),ae(i,x),ae(x,i);
        dep[0]=-1;
        get_dep(1,0);
        for(int i=1;i<=n;i++)
          maxdep=max(maxdep,dep[i]);
        dfs(1,0);
//      for(int i=1;i<=n;i++)
//        printf("%lld %lld\n",dp[i][0],dp[i][1]);
        printf("%lld\n",max(dp[1][0],dp[1][1]));
    }
    return (0.0);
}

:::: ::::info[T4]

/*
11:28 T4 looks like a great problem to steal pts.

12:20 noooooooooooooooooo i can just take the most slow pts. (maybe 0pts)
(da lian ing)
this noip is ruined.
i think 2= is hard for me. im too vegetable though.

12:42 why is this noip soooooooooooooo much dp.
i hate dp. its like T2T3 all dp. T4 is a shujujiegou maybe.
if T2T3T4 is all green+ problem, and my T1 got 100pts, i will be happy enough.
pts \in [0,104]

12:47 ok this is my 1st noip.
xiandemeishi,i think about T2.
*/

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long

const int N=5e4+5,M=1030;
ull mod;
int n,q,a[N],pre[N],pp[N];

signed main()
{
    freopen("query.in","r",stdin);
    freopen("query.out","w",stdout);
    mod=(ull)pow(2,64);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
      scanf("%lld",&a[i]),pre[i]=pre[i-1]+a[i];
//  for(int i=1;i<=n;i++)
//    pp[i]=pp[i-1]+pre[i];
////    for(int i=1;i<=n;i++)
//      for(int j=1;j<=n;j++)
//      {
//          int len=min({i,n-i+1,j});
//          int l=pp[i-1]-pp[max(0ll,i-1-j)];
//          int r=pp[min(n,i+j-1)]-pp[i-1];
//          temp[i][j]=r-l;
//      }
//  for(int i=1;i<=n;i++)
//  {
//      for(int j=1;j<=n;j++)
//        printf("%lld ",temp[i][j]);
//      puts("");
//  }
    scanf("%lld",&q);
    while(q--)
    {
        int l,r;
        scanf("%lld%lld",&l,&r);
//      if(l==r)
//      {
//          for(int i=1;i<=n;i++)
//          {
//              int len=min({i,n-i+1,l});
//              int l=pp[i-1]-pp[max(0ll,i-1-len)];
//              int r=pp[min(n,i+len-1)]-pp[i-1];
//              printf("%lld\n",r-l);
//          }
//      }
        ull ans=0;
        for(int i=1;i<=n;i++)
        {
            int temp=LLONG_MIN;
            for(int len=l;len<=r;len++)
                for(int j=max(i,len);j<=min(i+len-1,n);j++)
                  temp=max(temp,pre[j]-pre[j-len]);
            ans=(ans^(((ull)temp)*i%mod));
        }
        printf("%llu\n",ans);
    }
}

::::

弱省初中生部分中部微下。没救了。