本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-13 19:37:03

按照习惯，来个 blog 记录。

赛前

先是 $\color{purple}\text{pt}$ 大佬邀请，但我认为我太菜了，之前每次都拖他后腿，这次还是算了吧。

过了一个周左右，$\color{orange}\text{chb}$ 大佬邀请，$\color{gray}\text{本蒟蒻}$正好也不想单打独斗，加入了。

不管加入哪个队，都是 rating 最低的。

这次希望不拖后腿，然而不太可能。

过程

待填坑。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 20:31:36

yt->wf 经过了很长时间的思想准备，因为感觉这样对不起范老师和姜老师。

为了不用再学历史政治，初中进行长期停课，按照自己节奏训练，最后还是听从了我妈和我爸的想法来到 wf。

随后将 ytez 群的所有历史消息存储到本地作纪念，然后退出。

由于 wfyz 的要求，跳到了 9 年级。

感受是没啥变化，课业稍微紧张点，语文英语和原来难度变化不大，截至目前，讲的数学代数题都是 sb 题，几何题由于一些之前讲的公式没背，通常要比代数题花的时间长的多，但是都可做，顶天就是三角形相似，三角函数在几何证明中的应用。物理感觉全书最难的是电学，而化学主要难度在于背诵元素周期表和化合价，以及物品的俗名对应的化学式。

历史政治全都扔了。

这个班有位超前学物理和数学的，未央（wfyz 重点班）物理第三。时常会交流比较简单的高中数学题，他有时也会给我看未央的物理题，但是我一个字看不懂。我问过他是否会参加 PhO，他说得考到物理 A+ （大概是 wfyz 保送资格）

紧张的是数学拿不到 A+ 可能要挨批+不准停课，物理化学拿不到 A 可能没法停课。

这周末，USACO 一道题推不出正解，抱着死磕的心态，结果一题没交，爆零了。

ABC333，尝试了下比赛期间听歌，然后只做了 ABCD，perf 比前面几场的平均值低了 700 左右。

当晚 CF 再次尝试，然后认真打了 2h，只有 A 过的好成绩，上次至少是读错题了不是水平问题，但这次。。。。。已经一两年没出现过这种情况了。

THUPC 和 chb，wjr 组队。

chb 大佬和 wjr 大佬过了 4 题，献上诚挚的膜拜，而我只贡献了一发罚时。

一开场，我先开的 H，并立刻想出了一个 $O(n \log^3 n)$ 做法，事实上可以通过，但是我的 bug 太多了，没调出来（可能是太久没写 DS），发给队友，也没有结果。

近期比赛也频繁就差一点时间通过高分值题目，其中最离谱的两个是 CFR911 DE 都能想出来，但是时间只够一道题，结果 D 临结束最后一发正确代码因为编译器不同 CE 了，这也是我 CF 经历的唯一一次 CE 挂分；CFR909 G ，最后 10s 找出问题并成功修改，然后网速原因差 1s 提交上。

忽然想起，两个月前 rating 较快上涨的时期，跟别人聊天，我瞎 bb 说我即将经历 E->S，S->P，P->N。没过多久前两项成真了，这个状态，第三项也快了。虽说没啥关系，但还是不能再乱说话了。

我相信我从 Expert 掉到 Newbie 后能触底反弹。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-23 22:25:15

md，G 题会做但是没调出来。

B

我认为解释不如直接看代码

 cin>>a>>m>>l>>r;
 if(a<l)
 {
    printf("%lld\n",calc(r)-calc(l-1));
 }
 else if(a>=l&&a<=r)
 {
     printf("%lld\n",(a-l)\/m+1+(r-a)\/m);
 }
 else
 {
     printf("%lld\n",calc2(l)-calc2(r+1));
 }  

C

以下结论我认为很显然，不做解释。

如果 $n$ 是偶数，那么排序，然后贪心地 $(1,2)$ 一对，$(3,4)$ 一对 $\cdots \cdots$

如果 $n$ 是奇数，那么枚举要删的点，经过预处理可以 $O(1)$ 计算得出删除每个点之后的答案。

D

纯纯前缀和二分板子。

E

先预处理连通块，然后枚举每个点，看把他涂成绿色的连通块个数，思想简单就是写起来麻烦。

F

暂时不会。

G

稍微修改一下求割点的算法，使其标记上它所连接的连通块数量，这个稍微思考一下就能想出来。

#include <bits\/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int maxm = 8e6 + 5;
int n, m;
int id(int i, int j)
{
    return (i - 1) * m + j;
}
int head[maxn];
struct EDGE
{
    int to, nxt;
} edge[maxm << 1];
int cnt = 1;
typedef long long ll;
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
ll inv(ll a)
{
    return qpow(a, mod - 2);
}
void add(int u, int to)
{
    edge[++cnt].to = to;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
int dfn[maxn];
int low[maxn];
int cut[maxn];
int ids; \/\/ 时间戳
void print(int x)
{
    int lie=x%m;
    if(lie==0)lie=m;
    printf("%d %d\n",(x-1)\/m+1,lie);
}
void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++ids;
    register int child = 0; \/\/ 子树
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        register int to = edge[i].to;
        if (!dfn[to])
        { \/\/ 尚未访问过
            tarjan(to, fa);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u] && u != fa) \/\/ 需要经过u访问更早的祖先
            {
                cut[u]++;
            }
            if (u == fa) \/\/ 如果是根节点
            {
                child++; \/\/ 子树++
            }
        }
        low[u] = min(low[u], dfn[to]); \/\/ 没有父子关系的话，那么按普通边计算，更新u
    }
    if (child >= 2 && u == fa) \/\/ 这样根节点也是割点，因为删除它就会有两棵蒲通的树不连通
    {
        cut[u] = child-1;
    }
   \/\/ printf("u = ",u);
   \/\/ print(u);
   \/\/ printf("cut = %d\n",cut[u]);
}
char s[1005][1005];
bool chk(int i, int j)
{
    if (s[i][j] != '#')
        return 0;
    if (i < 1 || i > n)
        return 0;
    if (j < 1 || j > m)
        return 0;
    return 1;
}
bool td[1000005];
void dfs(int u)
{
    td[u] = 1;
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        int to = edge[i].to;
        if (!td[to])
            dfs(to);
    }
}
int ltkcnt;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s[i] + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (chk(i, j))
            {
                if (chk(i - 1, j))
                {
                    add(id(i - 1, j), id(i, j));
                    add(id(i, j), id(i - 1, j));
                }
                if (chk(i + 1, j))
                {
                    add(id(i + 1, j), id(i, j));
                    add(id(i, j), id(i + 1, j));
                }
                if (chk(i, j - 1))
                {
                    add(id(i, j - 1), id(i, j));
                    add(id(i, j), id(i, j - 1));
                }
                if (chk(i, j + 1))
                {
                    add(id(i, j + 1), id(i, j));
                    add(id(i, j), id(i, j + 1));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '#' && !dfn[id(i, j)])
            {
                tarjan(id(i, j), id(i, j));
            }
            if (s[i][j] == '#' && !td[id(i, j)])
            {
                dfs(id(i, j));
                ltkcnt++;
            }
        }
    }
  \/\/  printf("ltkcnt = %d\n", ltkcnt);
    ll ans = 0;
    ll ansct = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] != '.')
            {
                ansct++;
                bool ok=0;
                ok|=(s[i-1][j]=='#');
                ok|=(s[i][j-1]=='#');
                ok|=(s[i+1][j]=='#');
                ok|=(s[i][j+1]=='#');
                if(!ok)ans+=ltkcnt-1;
                else ans += (ltkcnt + max(0, cut[id(i, j)]));
            \/\/    printf("%d %d %d\n", i, j, (ltkcnt + cut[id(i, j)]));
                ans %= mod;
            }
        }
    }
    ans *= inv(ansct);
    printf("%lld", ans % mod);
    return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-23 18:07:54

背景

wfyz 的 lxn 教练要求用 2 月的时间测试我的学习能力，让我跳到 9 年级参加期末考试。

地点：凤凰学校
班级：9.4
Debuff1：8 年级几乎没上
Debuff2：考试前一天晚上发烧，考试第二天全天困
Buff：不用考历史政治
Prize：考试结束允许停课

Day 1

先考语文。

发现文常一如既往的不会。

反正文科本来就不行，心态非常的稳。

做着做着发现只剩一个小时，却还剩两篇作文，吓得够呛。

然后把速度提到最快，然后在还剩 50 min 开始作文。

第一篇小作文写谷爱凌比赛夺金场面，未加任何思考，10min 写完。

第二篇作文给出一段话，要求根据主旨写作文，用了 5min 构思，然后最后时刻结尾。

然后考政治
这个是用来休闲的，
然后我的卷子依次写了这些东西：

政治，$\frac{n!}{m!(n-m)!}$
有学政治的时间还不如【数据删除】
原神，启动！
Orz （后面是一些大佬，包括 cancan12345,cancan123456,Acaca_,Garry_HJR，Coffee_zzz,Rain_lyric,cxm1024,zhqwq,szhlg，OMG_78,lsxhyyds，kbwhy，klddt,krzqz,Anonymely,GS128 等人）
Common Unusual Rare Epic Legendary Mythic Ultra Super-Omega/Hyper
Newbie Pupil Specialist Expert Candidate Master Master International Master Grandmaster International Grandmaster Legendary Grandmaster
You're wrong. Here's why --Mike
Zh0ukangyang was removed from the rating! --Mike
Rest in peace --Mike

然后被监考的历史老师看见了，对着那串英文沉思了一会，还问 zh0ukangyang 是谁。我没回答，然后说我是对政治的态度问题，要求我第二天历史不允许这么干，不好说什么。

中午什么也不想干，睡觉。

下午先考的英语。

干脆改名叫阅读理解考试吧，全是阅读题。所有阅读理解都很快读懂，然而仅有的几个不会的单词出现在了翻译句子里，悲。

然后考物理，我原来以为是第二天物理，计划一下子打乱。

最后正常发挥。然后我和班里一个 PhOer（wfyz 物理 rk3） 的对了一下，他居然也不知道手机电池能不能改变电压，而我猜的选项和他相反，于是一起找了物理老师，很不幸，我错了。

Day2

不知道为什么很困，考试前也是这样。

先考数学，卷子标明 A 卷。

先发下答题卡来，我闻着纸挺香的，闻了一会发现马上开始考试了。

扇了自己几巴掌强制清醒。

考试考着考着感到很慌，因为我竟然一路秒了单选，多选，填空，这在平时是不可能的，我怀疑题里藏了陷阱，但并没有找到。

然后，做了前几道大题，仍然做法秒掉，只不过计算上出题人设下了一些坑，耗费了不少时间，导致最后仍然只有 0.5h 做最后两道大题。

这时候有些慌了，倒数第二道大题是个圆的综合题，我用垂径定理+黄金三角形 + 2 条辅助线 + 3 对全等三角形秒了前三问，此时我发现第四问不太好做，而最后的大题是我的强项。

然后暴力计算干掉了最后的大题，反过来看最后剩下的那一问，可惜时间不够了，这 3 分拿不到了。

如果不挂分就是 147/150，希望是这样，但不现实。

接下来考历史。

虽然我知道历史老师说什么并没用，但我还是选择了认真作答（因为 zz 无论做不做都是 D，历史就不一定了，上次我靠着抄卷子上的选择题材料拿了 B）

没啥好说的，做到我的极限后就考场睡觉，然后历史老师看见后被叫起来继续做，但实际上也干不了什么了。

中午啥也不想干，用来调整状态。

然而还是很困，而且自我扇了几巴掌后困意仍然贯穿了整个化学考试。
前面比较顺利，直到一道多选题，我选出了 3 个正确答案，但规定最多 2 个答案。

我很快慌了，不知道哪里出了问题，随着时间流逝，我不断重复推导，却没有任何结果，眼看着浪费了大把时间（至少 10min）随后放弃。

之后做题心里也变得很慌。

20min 后

化学老师：有个多选题出了错啊，这里改一下........

我：Fuck！！！！！！！！！！！！！！！！！！

直接后果就是我因为这道题浪费的时间没做完卷，与 A 等级无缘，心里把出题人祖宗问候了一遍。

然后结束了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-27 13:51:57

自己做出了 ABCDE，F 是个什么玩意啊。

A

如果忽略 $c$，那么 $a,b$ 无论如何可以匹配。

只要有一个位置可以在匹配 $a,b$ 的情况下不匹配 $c$，那么有解。

#include <bits\/stdc++.h>
using namespace std;
int T;
const int maxn=25;
char a[maxn],b[maxn],c[maxn];
int n;
void solve()
{
    scanf("%d",&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    scanf("%s",c+1);
    bool flag2=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==b[i])
        {
            if(c[i]!=a[i])
            {
                flag2=1;
            }
        }
        else
        {
            if(a[i]!=c[i]&&b[i]!=c[i])
            {
                flag2=1;
            }
        }
    }
    puts(flag2?"YES":"NO");
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

B

按照枚举三角形最长边长度考虑。

显然最长边在三角形中出现次数大于等于两次。

然后推个柿子就行了。

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int t,n;
int a[maxn];
int cnt[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            cnt[a[i]]++;
        }
        ll ans=0;
        ll pre=0;
        for(int i=0;i<=n;i++)
        {
            ans+=max(0ll,1ll*cnt[i]*(cnt[i]-1)*(cnt[i]-2)\/6ll);
            if(i!=0)
            {
               ans+=max(0ll,1ll*cnt[i]*(cnt[i]-1)*pre\/2ll);    
            }
            pre+=cnt[i];
        }
        printf("%lld\n",ans);
        \/\/ clean
        for(int i=0;i<=n;i++)cnt[i]=0;
    }
    return 0;
}

C

预处理正向和反向的捷径数量的前缀和。

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
int T;
const int maxn=1e5+5;
int n,m;
int a[maxn];
ll tagpre[maxn],tagsuf[maxn];\/\/ 在到达他之前经过了多少个捷径
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    a[0]=-1e9;
    a[n+1]=2e9+1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-a[i-1]<a[i+1]-a[i])
        {
            tagsuf[i-1]+=(a[i]-a[i-1]-1);
        }
        else
        {
            tagpre[i+1]+=(a[i+1]-a[i]-1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        tagpre[i]+=tagpre[i-1];
    }
    for(int i=n-1;i>=1;i--)
    {
        tagsuf[i]+=tagsuf[i+1];
    }
    scanf("%d",&m);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x<y)
        {
            printf("%lld\n",a[y]-a[x]-tagpre[y]+tagpre[x]);
        }
        else
        {
            swap(x,y);
            printf("%lld\n",a[y]-a[x]-tagsuf[x]+tagsuf[y]);
        }
    }
    \/\/ clean
    for(int i=0;i<=n+1;i++)
    {
        tagpre[i]=0;
        tagsuf[i]=0;
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0; 
}

D

注意，如果上一轮某一个 mob 及他的的左右邻居都还活着，那么他这一轮仍然活着，因为每一轮生命重置。综上，其实每一轮只需要考虑上一轮被击杀的怪的邻居（当然，不考虑已被击杀的怪）。

于是用链表维护存活的 monster。

然后先构建一个队列 qd，存放所有可能造成击杀的 monster，初始设置为全部 monster 加入。

每一轮依次进行一下操作：

1. 遍历可能造成影响的 monster 队列 qd，并统计被伤害的 monster 有哪些，以及分别受到的伤害，将所有受到伤害的 monster 加入队列 wait。
2. 遍历所有受到伤害的 monster 队列 wait，对于被杀死的 monster，将其从链表删除并加入队列 death。
3. 遍历队列 death，将其存活的邻居加入集合 qd2
4. 为了下一轮统计完整，遍历 qd2，将其存活邻居集合 qd3
5. 合并 qd2,qd3，并将 qd 替换为 qd2 和 qd3 的并集。

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
int T;
const int maxn=3e5+5;
int n;
int a[maxn],d[maxn];
struct List
{
    int lef[maxn],rig[maxn];
    void rebuild()
    {
        FOR(i,1,n)
        {
            lef[i]=i-1;
        }
        FOR(i,1,n-1)
        {
            rig[i]=i+1;
        }
        rig[n]=rig[n+1]=0;
        lef[0]=lef[n+1]=0;
    }
    void del(int pos)
    {
        rig[lef[pos]]=rig[pos];
        lef[rig[pos]]=lef[pos];
    }
}lst;
ll dam[maxn];
bool dead[maxn];
\/*
hack.in:  
1
4
1 1 1 2 
1 2 1 1 

hack.out
1 1 1 0


(heal 1,dam 1),(heal 2,dam 1),(heal 1,dam 2) 
*\/
void solve()
{
    scanf("%d",&n);
    FOR(i,1,n)
    {
        scanf("%d",&d[i]);
    }
    FOR(i,1,n)
    {
        scanf("%d",&a[i]);
    }
    \/\/ 按照我的习惯，d=damage=攻击
    lst.rebuild();
    queue<int> qd,death;
    set<int> wait,qd2,qd3;
    FOR(i,1,n)
    {
        qd.push(i);
    }
    FOR(rounds,1,n)
    {
     \/\/  printf("\n round %d\n",rounds);
        while(!qd.empty())
        {
            int u=qd.front();
         \/\/   printf("u = %d\n",u);
          \/\/  printf("lef = %d rig = %d\n",lst.lef[u],lst.rig[u]);
            if(lst.lef[u])
            {
                dam[lst.lef[u]]+=d[u];
                wait.insert(lst.lef[u]);
            }
            if(lst.rig[u])
            {
                dam[lst.rig[u]]+=d[u];
                wait.insert(lst.rig[u]);
            }
            qd.pop();
        }\/\/ 计算攻击
        int cntdeath=0;
        for(int u:wait)
        {
        \/\/\/	printf("dam[%d] = %d\n",u,dam[u]);
            if(dam[u]>a[u])
            {
                lst.del(u);
                death.push(u);
           \/\/     printf("death = %d,dam = %d\n",u,dam[u]);
                cntdeath++;
                dead[u]=1;
            }
            dam[u]=0;
        }\/\/ 处理死亡
        wait.clear();
        while(!death.empty())
        {
            int u=death.front();
            death.pop();
            if(lst.lef[u])qd2.insert(lst.lef[u]);
            if(lst.rig[u])qd2.insert(lst.rig[u]);
        }\/\/ 将死亡的mob 的邻居加入
    
        for(int v:qd2)
        {
            if(!dead[v])
            {
            	if(lst.lef[v])qd3.insert(lst.lef[v]);
            	if(lst.rig[v])qd3.insert(lst.rig[v]);
			}
        }
        for(int v:qd2)if(!dead[v])qd3.insert(v);
        for(int v:qd3)if(!dead[v])qd.push(v);
        qd2.clear();   
        qd3.clear();
        printf("%d ",cntdeath);  
    }
    FOR(i,1,n)dead[i]=0;
    printf("\n");
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

E

先将 $X$ 减一，这样只需要统计非空子序列了。

注意，一个长度为 $n$ 的上升子序列造成的贡献是 $2^n -1$，初步考虑从大到小依次构造不同长度的上升序列（注意，需要满足互相不影响），最终使得总贡献为 $X$。

但是需要注意，长度限制是 $200$，如果这样构造，那么总长度是 $O(log_2^2 n)$ 的，无法通过。

这时候，考虑一些数列之间进行共用。

此时，可以想到，先构造一个最大的上升序列 base 使得贡献不超过 $X$，然后让相邻元素差的很大以留出充足预备空间，然后，在后面降序插入数组，每插入一个数字 $x$，设序列 base 前 $id$ 个数字小于 $x$，那么总贡献将增加 $2^{id}$，这样就可以根据二进制完成构造了。

#include <bits\/stdc++.h>
using namespace std;
const int maxn=205;
typedef long long ll;
int T;
ll ans[maxn];
ll ar[maxn];
void solve()
{
	ll x;
	scanf("%lld",&x);
	x--;
	if(lower_bound(ans+1,ans+63,x)-ans==64)
	{
		puts("-1");
		return;
	}
	int unti=upper_bound(ans+1,ans+63,x)-ans-1;
	if(unti==64)
	{
		puts("-1");
		return;
	}
	x-=ans[unti];
	\/\/printf("unti = %d\n",unti);
	ar[1]=1;
	for(int i=2;i<=unti;i++)
	{
		ar[i]=ar[i-1]+1000;
	}
	int id=unti;
	while(x)
	{
	\/\/	printf("id = %d x = %lld\n",id,x);
		while(ans[id]+1>x)id--;
		x-=(ans[id]+1);
		ar[++unti]=ar[id]+1;		
	}
	printf("%d\n",unti);
	for(int i=1;i<=unti;i++)
	{
		printf("%d ",ar[i]);
	}
	printf("\n");
}
int main()
{
	ans[0]=0;
	for(int i=1;i<=63;i++)
	{
		ans[i]=(unsigned long long)(ans[i-1]+1)*2ll-1ll;
	} 
	scanf("%d",&T);
	while(T--)
	{
		solve();
	}
	return 0;
}

F

暂时没想出来。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-30 08:32:33

lxn 要求每人寒假至少出 4 题。

然后我构造了一道水题。

最初用 polygon.codeforces.com，并放 CF mushup contest 里请别人验题。

然后一切顺利，lsxhyyds，gwf01，yao23 先后通过。

然而。。。。我把题目搬到洛谷，并提交了他们和我原来的 ac 代码，看到了这样的美图：

每个人都 WA 在 #25，我比较了洛谷上的数据和原来 mushup 里的数据，发现 #25 的 input 是一样的，那是怎么回事呢？

想着可能是 generator 写炸了，看了一下，果然。generator 用 map 记录重边，如果随机生成重边，那么重新生成。但是我忘了在成功生成后将新生成的边记录到 map 里，所以可能有重边！！！

但是我的所有数据都通过了 validator 检验，怎么没报错？我又看了一眼 validator，居然十分巧合地，也没有记录读入的重边。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-30 13:16:50

后缀名不一样，所以暂时记录一下 CF 测试点格式向洛谷转换程序，主要解决 polygon 不方便直接搬到洛谷。

放到同一个文件夹下，代码中的 n 设置成实际测试点个数。

import os
r = os.system
for i in range(1,n+1):
    fn=""
    if i<10:
        fn="0"
    fn=fn+str(i)
    r("rename "+fn+" "+fn+".in")
    fn2=fn+".a"
    r("rename "+fn2+" "+fn+".out")
    

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-03 22:21:17

• 按照不同比赛类别分割，每种类别分别按照时间升序排列。

• 如果是 Atcoder 比赛，那么按照官方显示的 perf 计入 Atc perf。

• 如果是 CF 比赛，那么按照 Codeforces Performance 插件计入 CF perf

• 本文使用这个网站将 CF-AT 的 perf 互相转换：https://silverfoxxxy.github.io/rating-converter 。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-07 01:06:49

倒开不幸被卡。

G 被 hack 了，请忽略以下。

一张图描述状态：

G

可以想到 dp 做法，并且看起来最重要的两个量是：

1. 当前的结尾位置 $i$
2. 前 $i$ 个涂满，且延伸到 $j \ge i$ 位置同样全部涂满。

设状态 $dp_{i,j}$ 代表以 $i$ 结尾，前 $j$ 个涂满的最小代价。

以下对 dp 赋值默认是 chkmin

考虑转移：

• 第 $i$ 个向左涂：
  $dp_{i,max(y,i)} = min(dp_{k,y})$，注意 $k \lt i,y \ge i-a_i$
• 第 $i$ 个向右涂：
  $dp_{i,max(y,min(n,i+a_i-1))} = min(dp_{k,y})$，注意 $k \lt i,y \ge i-1$
• 第 $i$ 个不涂：
  $dp_{i,y} = min(dp_{k,y})$，注意 $k \lt i,y \ge i$

还有一种特殊情况，在样例的 testcase11 中可以看见。
这种情况就是 $a_i \ge i$，此时可以这样转移：
$dp_{i,min(n,k+a_k-1)} = 2$，注意 $k \lt i$

做完了。

简单分析一下，本算法复杂度 $O(n^3)$，最多 $10^4$ 组数据，$n \le 100$，$n$ 总和最多 $1000$，为了使运算量最大，出题人应该设置 $10$ 个 $n=100$ 的数据，此时运算量 $10^7$，稳过。

A-F

A-E 没做，F 一直 WA。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-10 00:02:21

距离上次赛时 AC 提交被 hack 过去了近 1.5 年，写篇题解纪念一下。分类讨论漏了一种情况都能过 pretests，难怪最终只过了这么点人。
在此感谢 160cm 对我赛时代码的 hack 数据，帮我找出我的错误。

大概思路

相信很多人读完题就能想到用 dp。
由于有 $n$ 个格子从左到右，每个格子分别决策，所以初步设想使用 $dp_i$ 代表假如以 $i$ 结尾（换句话说，$n=i$），答案是多少。

那么转移则从 $1$ 到 $n$ 枚举 $i$，然后从 $[0,i-1]$ 依次枚举 $j$，计算从 $dp_j$ 转移到 $dp_i$ 的答案。

这里有一个致命的问题，因为即使是最优方案下解决前 $i$ 个，但前 $i$ 个格子的涂色有可能延伸到 $i+1$ 或以后，而刚才设计的状态无法考虑此情况，从而导致答案算大。

另外，是否可以将状态更改为 $dp_i$ 表示答案？这里进行一些分析。前 $i$ 个涂满的考虑到每个格子只能决策一次，转移的时候（假设当前计算 $n = i$ 的答案，从第 $n = j$ 的答案转移），新操作的格子只能在 $[j+1,i]$ 选择，而这样既需要考虑最多前多少个格子可能被操作过，也需要考虑实际覆盖了前多少个格子。而本段开头设计的状态不能表示最多前多少个格子可能被操作过，所以是错误的。

另外如果有大佬设计了一维状态的 dp，请评论区回复。

最后，我设计的状态是 $dp_{i,j}$ 代表 $n=i$（即最多只操作前 $i$ 个格子），覆盖了前 $j$ 个格子的最小操作次数。

转移方法（以下方程默认等于号的实际作用是 checkmin）：

• 第 $i$ 个向左涂：
  $dp_{i,\max(y,i)} = \min(dp_{k,y})$，注意 $k \lt i,y \ge i-a_i$
• 第 $i$ 个向右涂：
  $dp_{i,\max(y,\min(n,i+a_i-1))} = \min(dp_{k,y})$，注意 $k \lt i,y \ge i-1$
• 第 $i$ 个不涂：
  $dp_{i,y} = \min(dp_{k,y})$，注意 $k \lt i,y \ge i$

还有一种特殊情况，在样例的 testcase11 中可以看见。
这种情况就是 $a_i \ge i$，此时可以这样转移：
$dp_{i,\min(n,k+a_k-1)} = 2$，注意 $k \lt i$

此时好像可以结束了？

如果你是这场比赛的选手，并且是 rated，那么这将是一个沉痛的教训（对不起我赛前临时改成了 unrated），因为这里漏掉了一种 pretests 中没有出现的情况。

注意，对于当前需要求解的 $dp_{i,j}$，不仅可以从 $dp_{k \lt i,y \in [1,n]}$ 等第一维小于 $i$ 的状态转移，还有可能从 $dp_{i,l \lt j}$ 通过选择一个位置在 $[j+1,i-1]$ 的格子向后涂色得到。

最后我的解决方案。