比赛地址
Pro: 6/7/11
Rank: 57/1019
[A] African Sort
题意
给一个排列p,每次可以选一个下标集合进行等概率打乱并花费集合大小的代价,求将p变成升序所需的最小代价的期望.
题解
队友推的式子,其中有一个ans_{n}=\sum_{i=2}^{n-1}\frac{ans_{i}}{i}+n
把环找出来计数下就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const long long int mo = 998244353;
long long int j[100005], ans[100005], ansi[100005], ansisum[100005];
int s[100005], used[100005], n, m;
long long int mi(long long int a, long long int n) {
if (n == 0) return 1;
if (n == 1) return a;
long long int m = mi(a, n/2);
m = m * m % mo;
if (n % 2) m = m * a % mo;
return m;
}
int main(){
j[0]=1;
for (int i=1;i<=100000;i++) j[i]=j[i-1]*i%mo;
ans[1] = ansi[1] = ansisum[1] = 0;
for (int i = 2; i <= 100000; i++) {
long long int k = (i + ansisum[i-1]) % mo;
k = k * j[i] % mo;
long long int f = (j[i]-j[i-1]+mo) % mo;
ans[i] = k * mi(f, mo-2) % mo;
ansi[i] = ans[i] * mi(i, mo-2) % mo;
ansisum[i] = (ansisum[i-1] + ansi[i]) % mo;
}
scanf("%d%d", &n, &m);
for (int t = 1; t <= m; t++) {
for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
for (int i = 1; i <= n; i++) used[i] = 0;
long long int nowans = 0;
for (int i = 1; i <= n; i++) if (used[i]) continue;
else {
used[i] = 1;
int k = 1;
int aim = i;
while(s[aim] != i) {
aim = s[aim];
used[aim] = 1;
k++;
}
nowans = (nowans + ans[k]) % mo;
}
printf("%lld\n", nowans);
}
return 0;
}
[B] Binary Vector
题意
随机生成n个n维的,由01组成的向量,求他们线性无关的概率.
题解
结论题.
f_{n}=\frac{2f_{n-1}+(2^{n}-1)}{2^{2n-1}}
队友说是抽象代数课期末考试原题...然后现场回忆下一波结论就给秒了.
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
long long int ni[20000005], ans[20000005], anss[20000005];
const long long int mo = 1000000007;
long long int mi(long long int a, long long int n) {
if (n == 0) return 1;
if (n == 1) return a;
long long int m = mi(a, n/2);
m = m * m % mo;
if (n%2) m = m * a % mo;
return m;
}
int main() {
ni[20000000] = mi(mi(2, 20000000), mo - 2);
for (int i = 20000000; i >= 1; i--)
ni[i-1] = ni[i] * 2 % mo;
ans[0] = 1; anss[0] = 0;
long long int fenzi = 0;
for (int i = 1; i <= 20000000; i++) {
fenzi = (fenzi * 2 + 1LL) % mo;
ans[i] = ans[i-1] * fenzi % mo * ni[i] % mo;
anss[i] = anss[i-1] ^ ans[i];
}
int T; scanf("%d", &T); while(T--) {
int n; scanf("%d", &n);
printf("%lld\n", anss[n]);
}
return 0;
}
[C] Combination of Physics and Maths
题意
给出一个矩阵,求它的一个子矩阵,使得子矩阵的和除以最后一行的和尽可能大.
题解
显然,最后的子矩阵只有一列,且确定了底边后,上面所有数都会被选中.直接枚举所有的情况取最大值就行了.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 210
#define INF 0x3f3f3f3f
using namespace std;
int T,i,j,n,m;
LL a[N][N],S[N][N];
struct Data{
LL x,y;
}s[N],Ans;
bool cmp(Data a,Data b){return (a.x*b.y>b.x*a.y);}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
Ans.x=0; Ans.y=1;
n=read(); m=read();
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
a[i][j]=read();
for (i=1;i<=n;i++){
for (j=1;j<=m;j++){
S[i][j]=S[i-1][j]+a[i][j];
s[j].x=S[i][j]; s[j].y=a[i][j];
}
sort(s+1,s+1+m,cmp);
if (cmp(s[1],Ans)) Ans=s[1];
}
printf("%.20lf\n",1.0*Ans.x/(1.0*Ans.y));
}
return 0;
}
[E] Easy Construction
题意&题解
签到题
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int s[5005];
int main() {
int n, k; cin >> n >> k;
if (n%2==1&&k!=0) {
printf("-1");
return 0;
}
if (n%2==0&&k!=n/2) {
printf("-1");
return 0;
}
if (n%2==1) {
s[n] = n;
int st = 1, en = n-1, cnt = n;
while(en >= st) {
s[--cnt] = en--;
s[--cnt] = st++;
}
} else {
s[n] = n;
s[n-1] = n/2;
int st = 1, en = n-1, cnt = n-1;
while(en >= st) {
s[--cnt] = en--;
s[--cnt] = st++;
}
}
for (int i = 1; i <= n; i++) printf("%d ", s[i]);
return 0;
}
[G] Grid Coloring
题意
给出一个n\times n的方格,要求用k种颜色对每条边进行染色.要求所有颜色出现的次数必须相同,不能构成同色环,每一横以及每一竖必须包含两种及以上的颜色,输出染色方案.
题解
简单构造.
至少队友是这么说的,榜被带歪了,这题真的不难
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int paint1[100000], paint2[100000], ans1[205][205], ans2[205][205];
int main() {
int t; cin >> t; while(t--) {
int n, k; scanf("%d%d", &n, &k);
if (k==1 || 2*(n+1)*n%k!=0 || n==1) {
printf("-1\n");
continue;
}
int cnt1 = 0, cnt2 = 0;
if (k%2==0) {
int p = 2*(n+1)*n/k;
for (int i = 1; i <= k/2; i++) for (int j = 1; j <= p; j++) paint1[++cnt1] = i;
for (int i = 1; i <= k/2; i++) for (int j = 1; j <= p; j++) paint2[++cnt2] = i+k/2;
} else {
int p = 2*(n+1)*n/k;
for (int j = 1; j <= p/2; j++) paint1[++cnt1] = 1;
for (int i = 2; i <= k/2+1; i++) for (int j = 1; j <= p; j++) paint1[++cnt1] = i;
for (int i = 2; i <= k/2+1; i++) for (int j = 1; j <= p; j++) paint2[++cnt2] = i+k/2;
for (int j = 1; j <= p/2; j++) paint2[++cnt2] = 1;
}
int now1 = 0, now2 = 0, p = 1;
for (int i = 1; i <= n; i++) {
if (i%2) for (int j = 1; j <= n+1; j++) {
if (p) { ans1[i][j] = paint1[++now1]; p = 0; }
else { ans1[i][j] = paint2[++now2]; p = 1; }
} else for (int j = n+1; j >= 1; j--) {
if (p) { ans1[i][j] = paint1[++now1]; p = 0; }
else { ans1[i][j] = paint2[++now2]; p = 1; }
}
}
for (int i = 1; i <= n; i++) {
if (i%2) for (int j = 1; j <= n+1; j++) {
if (p) { ans2[i][j] = paint1[++now1]; p = 0; }
else { ans2[i][j] = paint2[++now2]; p = 1; }
} else for (int j = n+1; j >= 1; j--) {
if (p) { ans2[i][j] = paint1[++now1]; p = 0; }
else { ans2[i][j] = paint2[++now2]; p = 1; }
}
}
for (int i = 1; i <= n+1; i++) {
for (int j = 1; j <= n; j++) printf("%d ", ans1[j][i]);
printf("\n");
}
for (int i = 1; i <= n+1; i++) {
for (int j = 1; j <= n; j++) printf("%d ", ans2[j][i]);
printf("\n");
}
}
return 0;
}
[H] Harmony Pairs
题意
求1到n内有多少对数满足A<B且d(A)>d(B).d(x)表示x的数位和.
题解
数位DP.同时枚举两个数的数位情况,多开两个变量,一个用来记录两数的数位差,另一个用来记录是否已经确定了两个数的大小关系.这题不需要考虑前导零的影响,所以不需要lead参数.
比赛的时候用的是两数各自的数位和表示的状态,于是毫无悬念地T了.姿势水平有待提高.
代码
#pragma GCC optimize(3)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
int i,len,flag;
LL Ans=0,sum=0;
int z[N];
char c[N];
LL f[N][1802][2][2][2];
IL void Upd(LL &x){(x>MOD)?x-=MOD:0;}
IL LL Dfs(int pos,bool limit,bool li,int s,bool tag){
LL sum=0,up=0,up2=0,i=0,j=0,p=0;
if (pos>len) return (s<900);
if (f[pos][s][limit][li][tag]!=-1) return f[pos][s][limit][li][tag];
up=(limit)?z[len-pos+1]:9;
up2=(li)?z[len-pos+1]:9;
for (i=0;i<=up;i++)
for (j=0;j<=up2;j++){
if (tag && j>i) break;
if (!tag) p=0; else p=(i>j)?0:1;
sum+=Dfs(pos+1,limit&&(i==up),li&&(j==up),s+i-j,p);
Upd(sum);
}
return f[pos][s][limit][li][tag]=sum;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%s",&c);
len=strlen(c);
int p=0;
for (i=len-1;i>=0;i--) z[++p]=c[i]-48;
memset(f,-1,sizeof(f));
Ans=Dfs(1,1,1,900,1);
cout<<Ans%MOD<<endl;
return 0;
}
[K] K-Bag
题意
一个序列被称为是K-Bag当且仅当它可以被看做是一堆长度为k的1到k的排列的拼接.现在给出一个长度为n的序列,判断它是不是一个K-Bag序列的子列.
题解
显然,给出的序列的开头与末尾可能含有一段不完整的排列,前后缀的合法性可以用map预处理出来.将前后缀去掉后,剩下的就可能是一个K-Bag序列了.接下来枚举这个序列的开头位置,假设是第i位,那么i到i+k-1,i+k到i+2k-1,等这些区间都要是合法排列.依次检查一遍即可.
快速判断合法排列有一个技巧,先给1到k赋一个2^{64}以内的数,然后算一下排列的异或值,再预处理一下给出序列的前缀异或值.这样,通过将一段区间的异或值与算好的排列异或值进行比较就可以判断它是不是排列了,正确性极高(好像错误率是\frac{1}{2^{64}}来着?).
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<unordered_map>
#include<ctime>
#include<cstdlib>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
int T,n,i,flag,k,x,j,ff;
int a[500010];
bool pre[500010],ne[500010];
LL b[500010],s[500010],ans;
unordered_map <int,bool> S;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
srand(time(NULL));
T=read();
for (i=1;i<=500000;i++) b[i]=((LL)rand() << 60) ^ ((LL)rand() << 45) ^ ((LL)rand() << 30) ^ ((LL)rand() << 15) ^ (LL)rand();
while (T--){
n=read(); k=read();
for (i=1;i<=n;i++) a[i]=read();
flag=0;
for (i=1;i<=n;i++) if (a[i]>k) flag=1;
if (flag){
puts("NO"); continue;
}
S.clear();
for (i=1;i<=n;i++) pre[i]=ne[i]=0;
for (i=1;i<=n;i++){
if (S.count(a[i])) break;
S[a[i]]=1; pre[i]=1;
}
S.clear();
for (i=n;i;i--){
if (S.count(a[i])) break;
S[a[i]]=1; ne[i]=1;
}
if (k>=n){
if (pre[n] || ne[1]) {
puts("YES"); continue;
}
for (i=1;i<n;i++)
if (pre[i] && ne[i+1]) {
puts("YES"); goto END;
}
puts("NO");
END:;
continue;
}
s[0]=0; ans=0; pre[0]=1; ne[n+1]=1;
for (i=1;i<=n;i++) s[i]=s[i-1]^b[a[i]];
for (i=1;i<=k;i++) ans^=b[i];
// cout<<ans<<endl;
flag=0;
for (i=1;i<=n;i++){
ff=0;
if (!pre[i] || i>k) break;
// cout<<i<<" "<<pre[i]<<endl;
for (j=i+k;j<=n;j+=k){
if ((s[j]^s[j-k]) != ans){
// cout<<j<<endl;
// cout<<(s[j]^s[j-k])<<endl;
ff=2; break;
}
if (j+k>n) {
if (!ne[j+1]) ff=1;
break;
}
}
if (!ff) {
flag=1; break;
}
}
if (flag) puts("YES"); else puts("NO");
}
return 0;
}
总结
栽在了H题上,用差来简化状态的手法应该很快就要想到的,看了题解后才发现距离正解真的只有一步之遥.前,中期没什么大的问题,后期的时间主要集中在想A和H上了.其实在发现H题实在没思路后应该开新题的,万万没想到J题的通过人数在封榜后暴增.A题推出来是一个意外之喜,希望之后可以保持状态.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第六场
本文地址: 2020牛客暑期多校第六场
