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

SD 省队集训第三轮 Day6，与教皇同分！

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

H 题赛时就差一行代码就过了，我该用什么描述我的心情。

A

a+b problem

B

排序板子题

C

字符串入门题。

D

显然剩下的子序列在原序列一定是连续的。

E

二分模板题。

F

对于每个数，枚举它的倍数就行了。
注意判断重复数字。

另外，对于只判断是否为 $1$ 的，能被这个 hack 卡成 TLE，我叉了 4 个人：

#include <bits\/stdc++.h>
using namespace std;
int n=2e5;
int main()
{
    printf("%d\n",1);
    printf("%d\n",n);
    for(int i=1;i<n;i++)printf("%d ",2);
    printf("2\n");
    return 0;
}  

G

同一行，同一列，同左下右上对角线，同左上右下对角线。
map 统计一下就行了吧。

另外如果用了 map.count，可以被 hack 到 TLE。

H

根据给定的边跑 dfs。
赛时我挂掉的原因是正反边都应该加上，而我只加了一条。

Pretests passed 代码：

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int t;
const int maxn=2e5+5;
int n,m;
int head[maxn];
struct EDGE
{
    int to,nxt;
    ll val;
}edge[maxn*2];
int cnt;
void add(int u,int to,ll val)
{
    edge[++cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int tag[maxn];
ll dis[maxn];
ll du[maxn];
bool no=0;
void dfs(int u,ll val,int _tag)
{
 \/\/   printf("u = %d\n",u);
    
    if(tag[u]!=0&&tag[u]!=_tag)return;
    tag[u]=_tag;
    if(no)return;
    if(dis[u]!=1e18)
    {
        if(dis[u]!=val)no=1;
        return;
    }
    dis[u]=val;
  \/\/  printf("dis[%d] = %lld\n",u,dis[u]);
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
    \/\/    printf("%d\n",to);
        dfs(to,dis[u]+edge[i].val,_tag);
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        FOR(i,1,m)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,-c);
        }
        FOR(i,1,n)dis[i]=1e18;
        FOR(i,1,n)
        {
            if(dis[i]==1e18)
            {
                dfs(i,0,i);
            }
        }
        if(no)puts("NO");
        else puts("YES");
        FOR(i,1,n)
        {
            head[i]=0;
            du[i]=0;
            tag[i]=0;
        }
        no=0;
        cnt=0;
    }
	return 0;
}
  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-22 09:17:30

没有 AK。

反正我不会直播吃键盘。

哪种方式吃键盘？

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-23 20:30:58

Vika 能不能让这场比赛难度分布正常一点

看到这题 *2400 以为是高大上算法。

其实只需要一个突破口。

设 $f_{i,j}$ 是第 $i$ 次操作后下标为 $j$ 的数，把这个式子写下来并展开。

容易发现，一个 $a$ 数列操作 $2^k$ 次，第 $i$ 个数就变成 $a_i \oplus a_{(i+2^k) \bmod n}$。

显然有解。

一个简单粗暴的做法，二分操作次数搞定。

$O(n \log^2 n$) 做法

后面更优做法待补充。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-26 21:15:54

很遗憾，SD 剃光头了。

题面附件。

https://www.luogu.com.cn/problem/U319219

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-29 00:05:56

我还是太菜了啊啊啊啊。

A

显然 $6 = 3!$。
也就是说所有 abc,acb,cab 之类的排列都可以解决，刚好对应 6 个子序列。
可以划分出 $[1,n],[n+1,2n],[2n+1,3n]$ 三个区间。

直接搞就行了。

#include <bits\/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
char s[maxn * 3];
int n;
char ord[4];
int ans[maxn*3];
int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    ord[1]='A';
    ord[2]='B';
    ord[3]='C';
    int num=0;
    do
    {
        num++;
        int minsum=0;
        int sum1=0,sum2=0,sum3=0;
        for(int i=1;i<=n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[1])sum1++;
        }
        for(int i=n+1;i<=2*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[2])sum2++;
        }
        for(int i=2*n+1;i<=3*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[3])sum3++;
        }
        minsum=min(sum1,min(sum2,sum3));
        sum1=sum2=sum3=0;
        for(int i=1;i<=n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[1])
            {
                if(sum1==minsum)continue;
                sum1++;
                ans[i]=num;
            }
        }
        for(int i=n+1;i<=2*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[2])
            {
                if(sum2==minsum)continue;
                sum2++;
                ans[i]=num;
            }
        }
        for(int i=2*n+1;i<=3*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[3])
            {
                if(sum3==minsum)continue;
                sum3++;
                ans[i]=num;
            }
        }
    } while (next_permutation(ord+1,ord+4));
    for(int i=1;i<=3*n;i++)
    {
        printf("%d",ans[i]);
    }
    return 0;
}  

B

由于操作可逆，可以把两个串向同一方向转化。

题目给定的 3 个可以互相转化的字符串统一成 abc，或其他的也行。

模拟一下可以看到，这些 abc 可以与其他任意字符交换。

所以做法：先把两个字符串的 abc,bca,cab 统一转化成 abc，转化出一个就删除一个，看最后两个字符串剩下的是否相等。

#include <bits\/stdc++.h>
using namespace std;
const int maxn=5e5+5;
char a[maxn],b[maxn];
int n;
bool vis[maxn];
bool vis2[maxn];
int main()
{
    scanf("%d",&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    vector<char> final_a,final_b;
    for(int i=1;i<=n;i++)
    {
        final_a.emplace_back(a[i]);
        int cnt=final_a.size();
        if(final_a.size()>=3)
        {
            string s={final_a[cnt-3],final_a[cnt-2],final_a[cnt-1]};
            if(s=="ABC" or s=="BCA" or s=="CAB")
            {
               final_a.pop_back();
               final_a.pop_back();
               final_a.pop_back(); 
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        final_b.emplace_back(b[i]);
        int cnt=final_b.size();
        if(final_b.size()>=3)
        {
            string s={final_b[cnt-3],final_b[cnt-2],final_b[cnt-1]};
            if(s=="ABC" or s=="BCA" or s=="CAB")
            {
               final_b.pop_back();
               final_b.pop_back();
               final_b.pop_back(); 
            }
        }
    }
    if(final_a.size()!=final_b.size())
    {
        puts("NO");
        return 0;
    }
    bool no=0;
    for(int i=0;i<final_a.size();i++)
    {
        no|=(final_a[i]!=final_b[i]);
    }
    puts(no?"NO":"YES");
    return 0;
}  

C 以后

还没看题。

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

纪念第一次赛时过 Ex && 做出 atc 2400+ 题目，虽然是个大水题。

• 做法 $1$
  考虑暴力枚举 $k$，暴力判定。
  显然会寄掉。

• 做法 $2$
  显然同一个字符串出现两次，第二次的答案一定大于第一次。
  其实一个字符串，只会对所有的循环节产生影响，而它本身的循环节种类显然是 $O(\sqrt{n})$ 量级的，可以参考因数数量，设本字符串长度为 $len$，那么最终造成的时间消耗是 $O(len \sqrt{len})$ 级别的。
  复杂度瓶颈在于同一个字符串出现多次。
  所以可以对字符串进行记忆化，对输入的字符串存储答案字符串，对最终形成的字符串（答案字符串）进行存在性标记。
  但朴素实现复杂度不变，主要瓶颈在于存储最终的答案字符串。

• 做法 $3$
  考虑字典树，此时我们对于答案字符串的记忆化，不再直接存储字符串，转而使用字典树，而记忆方式则是同时记录 $k$ 和答案字符串对应的字典树坐标。
  这样构造当前答案的时候，可以直接从原记录的字典树对应位置继续构造，而不用从头开始。
  复杂度 $O(len \sqrt{len})$。
  AC code
  另外由于循环节数量实际上一般远远少于根号，所以运行时间应该是接近 log 的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-30 23:26:20

爆零了。
而且是 Rated。

A

A 最优方案是删除最前面的 B。
B 最优方案是删除最前面的 A。

这么点东西都没想到，思维定势真的不能要啊。

B

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-30 23:31:16

学 OI 这么久终于能体验一下这种感觉了。

Time: 2023.7.30
Contest: Atcoder Grand Contest063
Solved: 0
Rating Change: -51
Color: cyan ---> green

曾有过一次，但是由于是多个账号，最高等级没变所以不变。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-03 18:18:16

手机写似乎不大方便。

求 $g^\sum\limit_{d|n} C_{n}^{d} \bmod m$

m 是非质数。