Preface
太FW了现在，纯纯给队伍拖后腿，马上要成为我们队CF Rating最低的了
但换句话说徐神和祁神都这么猛，我直接躺着被嘎嘎带飞好像也很爽啊
不管怎么样还是要多练，不过接下来可能要按专题重点突破了，明天队里开个会确定下大家的主攻方向再说
A. Prime Deletion
因为\(13\)和\(31\)都是质数，因此判断这两个数的位置关系即可
#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_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=15;
int t,pos[N]; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%s",s+1),i=1;i<=9;++i) pos[s[i]-'0']=i;
if (pos[1]<pos[3]) puts("13"); else puts("31");
}
return 0;
}
B. Two Binary Strings
由于开头和结尾确定，因此我们可以枚举两个位置\(i,j\)，当\(a_i=b_i=0\and a_j=b_j=1\and a_{[i+1,j-1]}=b_{[i+1,j-1]}\)时一定有解
当然其实可以直接枚举\(i,i+1\)，比赛时候铸币了看数据范围就滚去写\(O(n^2)\)的了，没写\(O(n)\)
#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_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=5005;
int t,n,f[N][N]; char a[N],b[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; scanf("%s%s",a+1,b+1); n=strlen(a+1);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) f[i][j]=0;
for (i=1;i<=n;++i)
{
if (!(f[i][i]=a[i]==b[i])) continue;
for (j=i+1;j<=n;++j)
if (!(f[i][j]=a[j]==b[j])) break;
}
bool flag=0; for (i=1;i<=n;++i) for (j=i+1;j<=n;++j)
if (a[i]=='0'&&b[i]=='0'&&a[j]=='1'&&b[j]=='1'&&(i+1<=j-1?f[i+1][j-1]:1)) flag=1;
puts(flag?"YES":"NO");
}
return 0;
}
C. Queries for the Array
被C题狠狠地腐乳了，还是靠ztc教我才会的，被狠狠地克制了
考虑序列的形态形如这样，先是若干个已知的位置，然后是若干个未知的位置
当遇到0时就把未知的位置的最后一个改成不合法的标记，然后如果有添加操作就在后面再加上若干个未知的位置
然后就是分情况讨论清楚即可，应该有更简单的做法的说
#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_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=200005;
int t,n,cnt; char s[N]; set <int> mx[2];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; scanf("%s",s+1); n=strlen(s+1);
bool flag=1,sign=0; int known=0,unknown=0,len=0;
for (i=1;i<=n&&flag;++i)
{
if (s[i]=='1')
{
if (sign) flag=0; known+=unknown; unknown=0;
}
if (s[i]=='0')
{
if (!sign)
{
if (!known&&unknown>1) sign=1,--unknown; else
if (known>=1&&unknown>=1) sign=1,--unknown; else flag=0;
}
}
if (s[i]=='+') sign?++len:++unknown;
if (s[i]=='-')
{
if (len>0) --len; else
if (sign) sign=0; else
if (unknown>0) --unknown; else
if (known>0) --known; else flag=0;
}
}
puts(flag?"YES":"NO");
}
return 0;
}
D. Sorting By Multiplication
傻逼题，比C简单到不知道哪里去了
考虑如果不能乘负数就是把序列分成\(m\)段，每段内的元素都是单调递增的，最后答案就是\(m-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_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=200005;
int t,n,a[N],suf[N],pre[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (suf[n]=1,i=n-1;i>=1;--i) suf[i]=suf[i+1]+(a[i]>=a[i+1]);
for (pre[1]=1,i=2;i<=n;++i) pre[i]=pre[i-1]+(a[i-1]<=a[i]);
int ans=min(suf[1]-1,pre[n]); for (i=2;i<=n;++i)
ans=min(ans,pre[i-1]+suf[i]-1); printf("%d\n",ans);
}
return 0;
}
E. Non-Intersecting Subpermutations
ORZ祁神，比赛时候教了我怎么做，但我因为一个铸币下标写错了没调出来
考虑DP，设\(f_{i,j}\)表示做了前\(i\)个位置，从位置\(i\)往前的\(j\)个数互不相同的方案数，转移的话有以下情况：
- \(f_{i,j}\times (k-j)\to f_{i+1,j+1}\)
- \(f_{i,j}\to f_{i+1,s}\)，其中\(s\in[1,j]\)
然后要计算答案的话由于题目要求区间不能相交，但我们贪心地每次一旦出现\(j=k\)的情况就直接计算它的贡献，\(f_{i,j}\times k^{n-i}\to ans\)，然后注意转移变成\(k\to f_{i+1,1}\)即可
复杂度\(O(nk)\)
#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_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=4005,mod=998244353;
int t,n,k,f[N][N],g[N][N],pw[N],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&k),pw[0]=i=1;i<=n;++i) pw[i]=1LL*pw[i-1]*k%mod;
for (f[1][1]=k,i=1;i<=n;++i)
{
for (j=k-1;j>=1;--j) inc(g[i][j],g[i][j+1]);
for (j=1;j<=k;++j) inc(f[i][j],g[i][j]);
for (j=1;j<=k;++j)
{
if (j==k)
{
inc(ans,1LL*f[i][j]*pw[n-i]%mod);
inc(f[i+1][1],1LL*f[i][j]*k%mod); continue;
}
inc(f[i+1][j+1],1LL*f[i][j]*(k-j)%mod);
inc(g[i+1][j],f[i][j]);
}
}
return printf("%d",ans),0;
}
Postscript
so weak……
- Educational Codeforces Round Rated 154educational codeforces round rated round codeforces rated based educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round educational codeforces balance round