A Move Right

题目大意

简单模拟：输入一个长度为字符串 $n$ 输出一个0以后将字符串前n-1个输出即可。

code

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
string s;
void solve()
{
    cin>>s;
    printf("0");
    for(int i=0;i<s.size()-1;i++)printf("%c",s[i]);
    return ;
}
int main()
{
    solve();
    return 0;
}

B Unique Nicknames

题目大意

给定n个人的名和姓询问是否可能对于每一个人的名不与其他人的名或姓相同或者是姓不与其他人的名或姓相同
即：如果一个人姓:aaa 名:bbb 其他所有人的名和姓中不出现aaa或者bbb就是YES 否则NO

思路

用map记录所有人的名姓出现的个数然后依次遍历所有人对于每一个人分情况讨论 1.名字与姓氏不同 那么只要map中名姓的个数都大于1就是NO. 2.名字与姓氏相同 那么map中该名字至少存在两个只要判断没有第三个这样的名姓即可

code

#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
map<string ,int>mp;
string a[110],b[110];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        mp[a[i]] ++;
        mp[b[i]] ++;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=b[i])
        {
            if(mp[a[i]]>1 && mp[b[i]]>1)
            {
                printf("No");
                return ;
            }
        }
        else
        {
            if(mp[a[i]]>2)
            {
                printf("No");
                return ;
            }
        }
    }
    printf("Yes");
    return ;
}
int main()
{
    solve();
    return 0;
}

C 1 2 1 3 1 2 1

题目大意

给定S1 = {1} Sn = Sn-1 , n , Sn-1
例如 S2 = 1 2 1 S3 = 1 2 1 3 1 2 1

思路

做法是字符串拼接但是注意字符中不存在10 需要特判处理一下。赛后dls教了一个骚操作 STL的写法basic_string<int>s 可以实现整形数组像字符串的拼接删除操作可以算一个加强版vector了下面放两种代码

code1

#include<iostream>
#include<algorithm>
using namespace std;
int n;
string s[100];
void solve()
{
    cin>>n;
    s[1] = "1";
    for(int i=2;i<=n;i++)
    {
        s[i] = s[i-1];
        s[i] += i+'0';
        s[i] += s[i-1];
    }
    int siz = s[n].size();
    for(int i=0;i<siz;i++)
    {
        if(s[n][i]>'9')printf("%d ",s[n][i]-'0');
        else printf("%c ",s[n][i]);
    }
    return ;
}
int main()
{
    solve();
    return 0;
}

code2

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
/*
S1 = 1  Sn = Sn-1 , n , Sn-1
例如 S2 = 1 2 1 S3 = 1 2 1 3 1 2 1
basic_string<int>s;可以实现整形数组的拼接 加强版vector
*/
int main()
{
    basic_string<int>s = {1};
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        s = s + basic_string<int>{i} + s;
    }
    for(int i=0;i<s.size();i++) cout << s[i] << " ";puts("");
    
    return 0;
}

D - Cylinder

题目大意

给定n个操作操作有两种类型
1.存入x个大小为c的数
2.从头取出x个数并询问取出的数字之和

思路

因为数据范围很大 x 与 c 的范围都是1e9 不可能一个个暴力的模拟存取过程。于是我们可以以每次操作为一个单位去存取
例如 1 4 5 此时存入队列里的是{4,5} 而不是四个5 。取的时候 2 3 取3个数,我们可以直接取出3个此时队列中的元素为 {1,5}即只剩一个5 。若是取的个数大于队首的个数可以将队首弹出队列再对下一个元素进行取操作即可

code

#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
struct node
{
    ll x,c;
};
deque<node>dq;
void solve()
{
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        ll op,x,c;
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld",&x,&c);
            dq.push_back({x,c});//存入
        }
        else
        {
            scanf("%lld",&c);
            ll ans = 0;
            while(c)
            {
                ll sum = min(c,dq.front().c);//取两者中数量最小的
                ans += sum * dq.front().x;
                c -= sum ;
                dq.front().c -= sum;
                if(!dq.front().c)dq.pop_front();//取空了弹出队列
            }
            printf("%lld\n",ans);
        }
    }
    return ;
}
int main()
{
    solve();
    return 0;
}

E - Max Min

此题解法很多博主自己是用了预处理的方法同学用的ST表+二分曾小格局的认为没有什么让人眼前一亮的解法了结果dls就掏出了状压DP这种让人眼前一黑的解法然后jls用的容斥也再让我眼前一黑，果然还是自己太菜了。

题目大意

给定长度为 $n$ 的数列求有多少个区间满足最大值为 $x$ 最小值为 $y$

思路

对于求解区间我们可以固定左端点求解右端点的取值区间范围那么 $r 2 ? r 1$ 即是此次的贡献。我们可以对每个点从后往前预处理出四个下标：该点右边最近的 $x$ , $y$ ,大于 $x$ ,小于 $y$ 的数的下标. 预处理出这些数据以后就可以确定端点了具体的结合代码和注释理解即可

code

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
#define ll long long
int n,x,y,a[N],b[N],c[N];
int Max[N],Min[N];
//a:原数组 b[i]:在i位置后的x的位置(包括自己) c[i]:在i位置后的y的位置(包括自己)
//Max[i]:在i位置后的大于x的数的位置(包括自己) Min[i]:在i位置后的小于y的数的位置(包括自己)
void solve()
{
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    Max[n+1] = n+1, Min[n+1] = n+1;
    //b,c为0说明不存在x,y Max和Min为n+1说明不存在大于x/小于y的数
    for(int i=n;i>=1;i--)//预处理
    {   
        b[i] = b[i+1];
        if(a[i]==y)b[i] = i;//自己若符合上
        
        c[i] = c[i+1];
        if(a[i]==x)c[i] = i;

        Max[i] = Max[i+1];
        if(a[i]>x)Max[i] = i;

        Min[i] = Min[i+1];
        if(a[i]<y)Min[i] = i; 
    }

    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(!b[i] || !c[i])continue ;
        int l = max(b[i],c[i]);//此区间要都包括x和y 于是左端点取两者最大值
        int r = min(Max[i],Min[i]);//又不能取到大于x和小于y的数于是右端点取两者最小值-1 这里因为计算区间长度是合法端点r-l+1 于是这里并没有-1直接抵消
        if(r < l)continue ;//l不能大于r
        ans += r - l;
    }
    cout<<ans;
    return ;
}
int main()
{
    solve();
    return 0;
}

小声：容斥的写法还没学文章最后会放大佬的讲解视频链接

F - Cards

这题赛时没写出来看了大佬视频Erik_Tse才明白

题目大意

给定n张卡片每张卡片正面一个数 pi 反面一个数 qi 其中pi和qi都是1~n的全排列求选择卡片的方案数选择卡片的方案要满足包括1-n所有数

思路

可以结合代码看
一张牌正面pi 反面qi 可以看做是pi连向qi的边因为p,q序列都是1~n的全排列所以把所有牌的图建起来以后
所有的点都是一条入边(->qi)一条出边(pi->) 所以图是由若干个大小不一的环组成

例如
1 2 3
2 1 3
图中有两个环 1->2->1 3->3(自环) 那么选中一条边就相当于选中一张牌要选中所有的序列
那么每个集合选择的边要包括集合所有的点选边的方案就是包括该集合点的不同方案
将所有环的选择方案乘起来即是所有的方案
要包括{1,2}集合有三种选法 1. 1->2 2. 2->1 3.则是两条边全选包括{3} 的方案有1个 3->3 ans = $3 ? 1 = 3$

对于1个点集与2个点集已经求出 f[1] = 1 f[2] = 3
对于大小为3的点集任选至少两条边或者3条边全选才能包括所有的点方案数f[3] = C(3,2) + 1 = 4
对于大小为4的点集最少选两条边才能包括所有点(必须选对边 res = 2) 任选3条边以及选4条边的方案都是可行的 f[4] = 2 + C(4,3) + 1 = 7
此时已经发现有递推公式 f[n] = f[n-1] + f[n-2]
于是我们只需要求环的大小即可 (并查集求集合大小)

code

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int MOD = 998244353;
/*
一张牌正面pi 反面qi 可以看做是pi连向qi的边 因为p,q序列都是1~n的全排列  所以把所有牌的图建起来以后
所有的点都是一条入边(->qi)一条出边(pi->) 所以图是由若干个大小不一的环组成

例如 
1 2 3
2 1 3
图中有两个环 1->2->1  3->3(自环) 那么选中一条边就相当于选中一张牌 要选中所有的序列 
那么每个集合选择的边要包括集合所有的点 选边的方案就是包括该集合点的不同方案
将所有环的选择方案乘起来即是所有的方案
要包括{1,2}集合有三种选法 1. 1->2  2. 2->1 3.则是两条边全选 包括{3} 的方案有1个 3->3 ans = 3 * 1 = 3

对于1个点集与2个点集已经求出 f[1] = 1  f[2] = 3 
对于大小为3的点集 任选至少两条边或者3条边全选才能包括所有的点 方案数f[3] = C(3,2) + 1 = 4
对于大小为4的点集 最少选两条边才能包括所有点(必须选对边 res = 2) 任选3条边 以及选4条边的方案都是可行的 f[4] = 2 + C(4,3) + 1 = 7
此时已经发现有递推公式 f[n] = f[n-1] + f[n-2] 
于是我们只需要求环的大小即可 (并查集求集合大小)

多边形选边要求包含所有点的方案数 递推求解
*/
int p[N];
int get(int x)
{
    if(p[x] != x) p[x] = get(p[x]);
    return p[x];
}
void merge(int x,int y)
{
    p[get(x)] = get(y);
}
int q[N],vis[N],f[N];
void solve()
{
    int n,x;
    cin >> n;

    f[1] = 1, f[2] = 3;
    for(int i=3;i<=n;i++) f[i] = (f[i-1] + f[i-2]) % MOD;
    for(int i=1;i<=n;i++) p[i] = i;
    for(int i=1;i<=n;i++) cin >> q[i];
    for(int i=1;i<=n;i++)
    {
        cin >> x;
        merge(x,q[i]);
    }
    for(int i=1;i<=n;i++) vis[get(i)] ++;
    ll ans = 1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) ans = ans * f[vis[i]] % MOD;
    }
    cout << ans;
}
int main()
{
    solve();
    return 0;
}