首页 > 其他分享 >ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）

ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）

时间：2023-12-02 17:14:00浏览次数：31  
标签：AtCoder ARTIS Contest int CI typedef long include define

Preface

先补一下这场ARC的博客，因为在来回合肥的路上一直在想这场的CD，所以有空后就先把这场补了

A - <Inversion>

不难发现对于一段连续的<，设其长度为\(x\)，则它最少要贡献\(\frac{x(x+1)}{2}\)的答案

而我们很容易构造一种方案刚好满足这个下界，只要让每段的结束比下一段的开头大很多即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=250005;
int n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%d%s",&n,s+1); LL ans=0; int lst=-1;
	for (i=1;i<n;++i) if (s[i]=='<')
	{
		if (!~lst) continue; ans+=1LL*(i-lst)*(i-lst+1)/2LL; lst=-1;
	} else if (!~lst) lst=i;
	if (~lst) ans+=1LL*(n-lst)*(n-lst+1)/2LL;
	return printf("%lld",ans),0;
}

B - Arbitrary Nim

首先若\(\oplus_{i=1}^n a_i\ne 0\)则答案显然为\(-1\)，否则考虑用SG函数来推一推

手玩很容易发现\(SG(x)=x\bmod (k+1)\)，考虑要让最后的SG函数发生变化，则显然就是要找一个最大的且出现次数为奇数的数\(y\)，那么答案就是\(y-1\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=250005;
int n,x,sum; map <int,int> c;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; int ret=0; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&x),++c[x],sum^=x;
	if (sum) return puts("-1"),0;
	for (auto it=c.rbegin();it!=c.rend();++it)
	if (it->se%2==1) { ret=it->fi-1; break; }
	return printf("%d",ret),0;
}

C - Swap Characters

我是大傻逼，这题祁神提示了我114514次才会做，菜的离谱

直接考虑能变化到的字符串有点难以下手，不妨先考虑以下问题：

给定\(S\)与\(T\)，求从\(S\)最少要进行多少次操作才能得到\(T\)

手玩一下会发现对于一对AB和BA的位置，我们肯定是直接交换最优，对于其它两种情况也是同理

否则如果有解最后剩下的一定是相同个数的AB,BC,CA这种循环变化的，我们可以用两次操作把每一对数减少\(1\)

知道了这个后我们就可以考虑直接枚举最后每种变化的个数，然后直接可重全排列算方案数即可

注意到自由量只有四个，即循环变化的次数、AB与BA的个数、BC与CB的个数、AC与CA的个数

复杂度\(O(n+k^4)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=250005,mod=998244353;
int n,m,fact[N],ifac[N],c[3],ans; char s[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int calc(CI x,CI y,CI z)
{
	if (x<y+z) return 0;
	return 1LL*fact[x]*ifac[y]%mod*ifac[z]%mod*ifac[x-y-z]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,l; for (scanf("%d%d%s",&n,&m,s+1),init(n),i=1;i<=n;++i) ++c[s[i]-'A'];
	for (l=0;l*2<=m;++l) for (i=0;i+l*2<=m;++i) for (j=0;j+i+l*2<=m;++j) for (k=0;k+j+i+l*2<=m;++k)
	(ans+=(l?2LL:1LL)*calc(c[0],l+i,j)*calc(c[1],l+k,i)%mod*calc(c[2],l+j,k)%mod)%=mod;
	return printf("%d",ans),0;
}

D - Maximize Update

这个题也很劲啊，想了半天只会一个\(O(n^4)\)的暴力区间DP，后面看了题解才发现连第一步的关键转化都没想到

首先我们考虑对于某种涂色方案，构造如下的一个序列\(\{a_1,a_2\cdots,a_k\}\)来代表它

其中\(k\)即为涂色的次数，而\(a_i\)则表示在第\(i\)次涂色中变黑的方格的编号（有多个就任取一个）

那么现在问题转化为求一个合法的且长度最长的格子序列，考虑对于某个序列我们要怎样验证其是否合法

正着做不好考虑，我们可以倒过来想，假设初始时所有操作都被进行了，\(i\)从\(k\)到\(1\)：

  • 检验\(a_i\)是否是黑色的，若为白色则不合法
  • 将所有包含\(a_i\)的区间\([L_j,R_j]\)的影响撤销

考虑这么做的好处，当我们选择了某个点\(a_i\)后，由于所有经过它的区间都不能再考虑了，因此问题会被划分成\([1,a_i-1],[a_i+1,n]\)两个子问题

因此可以考虑区间DP，设\(f_{l,r}\)表示仅考虑在区间\([l,r]\)的修改时序列的最长长度，转移方程很简单但需要快速确定某个位置\(m\)是否可以被选出

这个问题等价于询问仅考虑包含在\([l,r]\)中的所有修改区间，是否存在至少一个区间覆盖了\(m\)

我们可以统计出\(c_{l,r}\)表示包含在\([l,r]\)中的区间个数，这样只用看\(c_{l,m-1}+c_{m+1,r}\)是否等于\(c_{l,r}\)即可

总复杂度\(O(n^3)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=505;
int n,m,x,y,f[N][N],g[N][N];
inline int DP(CI l,CI r)
{
	if (l>r) return 0; if (~f[l][r]) return f[l][r];
	int ret=0; for (RI i=l;i<=r;++i)
	if (g[l][i-1]+g[i+1][r]!=g[l][r])
	ret=max(ret,DP(l,i-1)+DP(i+1,r)+1);
	return f[l][r]=ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d",&x,&y),g[x][y]=1;
	for (i=1;i<=n;++i) for (j=i;j<=n;++j) g[i][j]+=g[i][j-1];
	for (j=1;j<=n;++j) for (i=j;i>=1;--i) g[i][j]+=g[i+1][j];
	//for (i=1;i<=n;++i) for (j=i;j<=n;++j) printf("g[%d][%d] = %d\n",i,j,g[i][j]);
	return memset(f,-1,sizeof(f)),printf("%d",DP(1,n)),0;
}

Postscript

ARC稳定做不出C，咋回事呢

标签：AtCoder,ARTIS,Contest,int,CI,typedef,long,include,define
From： https://www.cnblogs.com/cjjsb/p/17871855.html

相关文章

  • The 2021 Sichuan Provincial Collegiate Programming Contest
    Preface下下周还要去打重庆市赛，最近就找些省赛来练练手不得不说省赛的签到题是真的多，人均10+的过题看起来还是很恐怖的这场虽然因为徐神缺席，而且前面的题目都让祁神来写导致罚时略高，但无所谓反正最后也摸到了11题（主要是没有字符串）A.Chuanpai某不知题意的签到#include<bits......
  • 像使用stl一样使用线段树 ——AtCoder Library(转载https://zhuanlan.zhihu.com/p/459
    地址：https://zhuanlan.zhihu.com/p/459579152 我这里翻译一下官方的文档。首先需要满足几个性质。(注意 ∗ 是个操作，不是单纯的一个乘号)1)操作满足结合律即 (a∗b)∗c=a∗(b∗c)2)操作需要有个幺元（基本元/单位元）a∗e=e∗a=a如果你有这个一个序列S，长度为N ，接下......
  • Atcoder-Countings4
    Atcoder-Countings4[ABC231G]BallsinBoxesProblem有\(n\)个盒子，初始时第\(i\)个盒子内有\(a_i\)个小球，进行\(k\)次操作后，每次操作等概率随机选择一个盒子放入一个小球，设\(k\)次操作后每个盒子的小球个数为\(b_i\)，那么得分为\(\prod_{i=1}^nb_i\)。求出期望得分......
  • AtcoderDP1
    AtcoderDP1收录非计数dp题。[ABC227F]TreasureHunting（2323）Problem给你一个\(N\timesM\)的矩阵，你需要从坐标\((1,1)\)走到坐标\((N,M)\)去，每次只能向右或者向下走。坐标\((i,j)\)的价值是\(A_{i,j}\)。我们定义一条路径的价值是，这条路径经过的坐标的前\(K\)......
  • The 2023 ICPC Asia Hefei Regional Contest
    目录写在前面赛时FEJGC补题写在最后写在前面赛时题目按照过题顺序排序，赛后补题按照个人向难度排序。省流版：要寄了吗？没寄。赛时F开局我正开，过了五分钟发现已经有人手刹了F了，几分钟之内大屏幕上一车提交，看了一下发现是超级签到于是Nebulyu上机开写。冲完之后发现T了？？？？\(10......
  • AtCoder Beginner Contest 330
    B-MinimizeAbs1思维题题意：给定一个范围，你选择一个数，使得思路：如果A[i]在l，r中间，那么直接打印就行，如果不是就打印就近的usingnamespacestd;voidsolve(){ intn,l,r; cin>>n>>l>>r; for(inti=1;i<=n;i++){ intx; cin>>x; if(x<l){ cout<<l<<"......
  • AtCoder Beginner Contest 326
    A-2UP3DOWN#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){inta,b;cin>>a>>b;if(a<bandb-a<=2)cout<<"Yes\n";elseif(a>banda......
  • AtCoder Beginner Contest 322
    A-FirstABC2#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definempmake_pairusingvi=vector<int>;usingpii=pair<int,int>;voidsolve(){intn;strings;cin>>n>>s;......
  • AtCoder 329. E - Stamp (搜索 + 思维
    importjava.util.Scanner;classMain{staticintn,m;staticStrings,t;staticStringBuilderox;/***思路:*思路的大门:题目要要求把x变成s,我们可以反过来,把s变成只有#的x,所以我们就有了思路*1.从前......
  • TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
    TOYOTASYSTEMSProgrammingContest2023(AtCoderBeginnerContest330)A-CountingPassesintmain(){IOS;cin>>n>>m;intans=0;rep(i,1,n)cin>>k,ans+=k>=m;cout<<ans;return0;}B-......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99