ACM暑期集训第二场
比赛地址
[A]String
题意
给出一个01串，需要把其切分为数段，使得每一段的字典序都是该段01串进行循环变换后最小的。求最小切分次数。
题解
首先先去掉先导1和后导0。然后把串切分为形式为00001111这样的数个串，之后暴力拼接。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char s[205];
int k[205];
int cnt[205], tot;
int st[205], en[205];
int cmp(int a, int b, int c, int d) {
int len1 = b-a+1;
int len2 = d-c+1;
int minlen = min(len1, len2);
for (int i = 0; i < minlen; i++)
if (s[a+i] > s[c+i]) return -1;
else if (s[a+i] < s[c+i]) return 1;
if (len1 > len2) return -1;
return 0;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
memset(s, 0, sizeof(s));
memset(k, 0, sizeof(k));
memset(cnt, 0, sizeof(cnt));
tot = 0;
scanf("%s", s);
int start = 0;
for (int i = 0; i < strlen(s); i++) {
if ((s[i] == '1' && s[i+1] == '0') || i == strlen(s) - 1) {
++tot;
st[tot] = start;
en[tot] = i;
start = i+1;
}
}
int p = tot;
for (int i = 1; i <= p; i++) {
for (int j = tot-1; j >= 1 ; j--) {
int k = cmp(st[j], en[j], st[j+1], en[j+1]);
if (k != -1) {
en[j] = en[j+1];
for (int l = j+1; l < tot; l++) {
st[l] = st[l+1];
en[l] = en[l+1];
}
tot--;
j--;
}
}
}
for (int i = 1; i <= tot; i++) {
for (int j = st[i]; j <= en[i]; j++) printf("%c", s[j]);
printf(" ");
}
cout << endl;
}
return 0;
}
[B]Irreducible Polynomial
题意
给出一个多项式，判断是否在有理数域上可约。
题解
根据高代知识，次数高于2次必定可约。2次判断是否有根，有根则可约。1次及0次必定不可约。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
if (n >= 3) {
int flag = 1;
int k; scanf("%d", &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &k);
if (k) flag = 0;
}
printf("No\n");
continue;
} else if (n <= 1) {
int k; for (int i = 1; i <= n+1; i++) scanf("%d", &k);
printf("Yes\n");
continue;
} else {
long long int a, b, c;
cin >> a >> b >> c;
long long int b2 = b*b;
long long int ac = 4 * a * c;
if (ac <= 0) {
printf("No\n");
continue;
} else if (b2 >= ac) {
printf("No\n");
continue;
} else {
printf("Yes\n");
continue;
}
}
}
return 0;
}
[C]Governing sand
题意
有n堆树，每堆树有一个高度，树的总数，和砍去一棵树的代价。现在需要砍掉一些树，使得最高的树占树的总数的一半以上。求最小砍树代价。
题解
枚举最高的树的高度，比它高的树全部砍掉，如果数目仍达不到一半，则再砍一些低的树。这时对砍一棵树的代价二分答案，计算砍多少价值及一下的树可以满足条件。每当处理完一个高度的树后，按照代价把其扔进一个序列中。因为代价至多为200，所以可以使用分块维护。每10价值为1块。故时间复杂度为O(20nlogC)
需要注意一些细节，以及long long一定要开全。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,j,p;
LL z[N],co[N],Co[N],s[N],S[N],tot[N],Tot[N];
LL Ans,cnt,ss,low,high,mid,sum,q;
map <int,LL> M,id;
struct Tree{
int h;
LL c,p;
}t[N];
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline bool cmp(Tree a,Tree b){return a.h<b.h;}
inline void Put(int x){
int i=0;
s[t[x].c]+=t[x].p; co[t[x].c]+=t[x].c*t[x].p;
i=(t[x].c/20)+1;
S[i]+=t[x].p; Co[i]+=t[x].c*t[x].p;
}
int main(){
while (~scanf("%d",&n)){
M.clear(); id.clear();
memset(t,0,sizeof(t)); memset(z,0,sizeof(z));
memset(s,0,sizeof(s)); memset(S,0,sizeof(S));
memset(co,0,sizeof(co)); memset(Co,0,sizeof(Co));
memset(tot,0,sizeof(tot)); memset(Tot,0,sizeof(Tot));
Ans=(LL)INF*INF; cnt=0; Ans=2*Ans;
for (i=1;i<=n;i++)
scanf("%d%lld%lld",&t[i].h,&t[i].c,&t[i].p);
sort(t+1,t+1+n,cmp);
for (i=1;i<=n;i++) M[t[i].h]+=t[i].p;
for (i=1;i<=n;i++){
if (t[i].h==t[i-1].h){
z[z[0]]+=t[i].c*t[i].p; tot[z[0]]+=t[i].p;
continue;
}
z[++z[0]]=t[i].c*t[i].p; tot[z[0]]+=t[i].p; id[t[i].h]=z[0];
}
for (i=2;i<=z[0];i++) z[i]+=z[i-1];
for (i=1;i<=z[0];i++) Tot[i]=Tot[i-1]+tot[i];
for (i=1;i<=n;i++){
if (t[i].h==t[i-1].h) continue;
for (j=i-1;t[j].h==t[i-1].h&&j;j--) Put(j);
sum=0; cnt=0;
cnt=z[z[0]]-z[id[t[i].h]];
sum=tot[id[t[i].h]];
if (Tot[id[t[i].h]]<=2*sum-1) {
Ans=Min(Ans,cnt); continue;
}
sum=Tot[id[t[i].h]]-(2*sum-1);
q=0;
for (j=1;j<=200;){
p=(j/20)+1;
if (q>=sum) break;
if (q+S[p]<=sum){
q+=S[p]; cnt+=Co[p]; j=p*20;
} else {
if (q+s[j]>=sum){
cnt+=(sum-q)*(LL)j;
break;
} else {
q+=s[j]; cnt+=co[j]; j++;
}
}
}
Ans=Min(Ans,cnt);
}
printf("%lld\n",Ans);
}
return 0;
}
[D]Number
题意
给出一个数p，构造一个n位数能整除p
题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
int n, p;
scanf("%d%d", &n, &p);
int len = 0;
int q = p;
while(q) {
len++;
q /= 10;
}
if (n < len) {
printf("T_T");
} else if (n == len) {
printf("%d", p);
} else {
printf("%d", p);
for (int i = 1; i <= n-len; i++) printf("0");
}
return 0;
}
[E]Find the median
题意
有n个操作，每个操作给出一个区间[l,r]。初始时有一个空序列，每进行一次操作，则把l,l+1,…,r添加到序列中。每次操作完毕后求该序列的中位数。
题解
考虑到区间范围高达1e9,所以需要对区间进行离散化。离散化完毕后建立线段树，线段树上每个节点维护一段原区间。每次先进行区间加1的操作，树上的节点记录下这段区间中一共有多少个数。然后算出中位数的位置，再进行区间查询，查到叶子节点后，根据这段区间被覆盖的次数进而计算出答案。
需要注意的是为了防止离散后的区间相互拼接到一起导致WA，需要把区间变成左闭右开再离散化。因为这道题卡内存，所以线段树不能存左右端点是多少。具体细节见代码。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 400010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,cnt;
LL a1,a2,b1,b2,c1,c2,m1,m2,Ans,L,R,sum;
int x[N],y[N],l[N],r[N],c[N*2],C[N*2];
map <int,int> M,M2;
struct Tree{
int len,lz;
LL sum;
}t[N*8];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Maketree(int x,int low,int high){
int mid=(low+high)>>1;
if (low==high){
t[x].len=C[low+1]-C[low];
return;
}
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
t[x].len=t[l(x)].len+t[r(x)].len;
}
inline void Push(int x){
LL p=t[x].lz;
t[l(x)].lz+=p; t[r(x)].lz+=p;
t[l(x)].sum+=(LL)p*t[l(x)].len;
t[r(x)].sum+=(LL)p*t[r(x)].len;
t[x].lz=0;
}
inline void Add(int x,int l,int r,int low,int high){
int mid=(l+r)>>1;
if (l==low&&r==high){
t[x].sum+=t[x].len; t[x].lz++; return;
}
if (t[x].lz) Push(x);
if (high<=mid) Add(l(x),l,mid,low,high);
else if (low>mid) Add(r(x),mid+1,r,low,high);
else Add(l(x),l,mid,low,mid),Add(r(x),mid+1,r,mid+1,high);
t[x].sum=t[l(x)].sum+t[r(x)].sum;
}
inline LL Query(int x,int l,int r,LL y){
int mid=(l+r)>>1;
LL p=0;
if (l==r) {
p=t[x].sum/(LL)t[x].len;
return (LL)C[l]+(y-1)/p;
}
if (t[x].lz) Push(x);
return (y<=t[l(x)].sum)?Query(l(x),l,mid,y):Query(r(x),mid+1,r,y-t[l(x)].sum);
}
int main(){
scanf("%d",&n);
scanf("%d%d%lld%lld%lld%lld",&x[1],&x[2],&a1,&b1,&c1,&m1);
scanf("%d%d%lld%lld%lld%lld",&y[1],&y[2],&a2,&b2,&c2,&m2);
for (i=3;i<=n;i++){
x[i]=((LL)a1*x[i-1])%m1;
x[i]=(x[i]+(LL)b1*x[i-2]+c1)%m1;
y[i]=((LL)a2*y[i-1])%m2;
y[i]=(y[i]+(LL)b2*y[i-2]+c2)%m2;
}
for (i=1;i<=n;i++) l[i]=Min(x[i],y[i])+1,r[i]=Max(x[i],y[i])+2;
for (i=1;i<=n;i++) c[++c[0]]=l[i],c[++c[0]]=r[i];
sort(c+1,c+1+c[0]);
cnt=0;
for (i=1;i<=c[0];i++)
if (!M[c[i]]) M[c[i]]=++cnt,C[cnt]=c[i];
cnt--;
Maketree(1,1,cnt);
for (i=1;i<=n;i++){
L=M[l[i]]; R=M[r[i]]-1; sum+=(LL)(r[i]-l[i]);
Add(1,1,cnt,L,R); Ans=Query(1,1,cnt,(sum+1)/2);
printf("%d\n",Ans);
}
return 0;
}
[I]Chessboard
题意
构造一个k*k的棋盘，每个格子上填一个不小于m正整数，使得不同行不同列的k个格子中的数加起来相同，且不超过n。求方案数。
题解
首先抛开限制，先考虑构造一个k*k的棋盘，不同行不同列的格子中的数加起来总和为T的方案数。先定义两种矩阵：
A_i:第i行为1，其余行为0；B_i:第i列为1，其余列为0
则符合题意的矩阵C一定满足以下形式：
C=\sum_{i=1}^ka_iA_i+\sum_{i=1}^kb_iB_i
其中的系数非负，正确性显然。
因为要保证总和为T，则有
\sum_{i=1}^ka_i+\sum_{i=1}^kb_i=T
则方案数为
C_{T+2k-1}^{2k-1}
但是这些选数方案有重叠，当a全为正数时，让a全部减一，b全部加一，得到的矩阵相同，但是被多计数了一次。所以真正的方案数为
f(k,T)=C_{T+2k-1}^{2k-1}-C_{T+k-1}^{2k-1}
注意后一项可能无意义，意味着a不能全为正数，这种情况要排除掉。
现在考虑加上限制后的情况，如果构造k*k的矩阵,每个数不小于m，总和为T，可以去掉限制，将总和变为T-k*m,再使用上面的式子计算即可。最终答案为：
\sum_{k=1}^{INF}\sum_{T=mk}^{n}f(k,T-mk)
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 4010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
int n,m,i,j,T;
LL Ans;
LL ml[N],nml[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline double Max(double a,double b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline LL Mi(LL x,LL y){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
inline void Ready(){
int i=0;
ml[0]=ml[1]=1;
for (i=2;i<=4000;i++) ml[i]=((LL)ml[i-1]*i)%MOD;
for (i=0;i<=4000;i++) nml[i]=Mi(ml[i],MOD-2);
}
inline LL f(int k,int s){
LL p=1,q=1;
p=ml[s+2*k-1]; q=ml[s+k-1];
p=(p*nml[2*k-1])%MOD; q=(q*nml[2*k-1])%MOD;
p=(p*nml[s])%MOD;
if (s-k>=0) q=(q*nml[s-k])%MOD; else q=0;
return (p-q+MOD)%MOD;
}
int main(){
T=read();
Ready();
while (T--){
scanf("%d%d",&n,&m);
Ans=0;
for (i=1;i<=INF;i++){
if (m*i>n) break;
for (j=m*i;j<=n;j++){
Ans=(Ans+f(i,j-m*i))%MOD;
}
}
printf("%lld\n",Ans);
}
return 0;
}
[J]A+B problem
题意
定义f(x)=x的各位倒序排列值。求f(f(a)+f(b))
题解
从名字就可以看出是签到题
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 200010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T;
LL a,b,c,d;
LL z[100];
inline int Abs(int x){return (x<0)?-x:x;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
LL f(LL x){
int i=0;
LL y=0;
z[0]=0;
while (x){
z[++z[0]]=x%10; x/=10;
}
for (i=1;i<=z[0];i++) y=y*10+z[i];
return y;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%lld%lld",&a,&b);
c=f(a); d=f(b);
printf("%lld\n",f(c+d));
}
return 0;
}
总结&吐槽
这次比赛总共做出5题，达到了平均水平。差一点做出了E，最后时间不够没能调完。
中间因为各种奇怪的问题吃了很多罚时，比如B题没有整明白出题人对可约的定义，A题上来口胡了几个不靠谱的做法，之后才证明有漏洞。C题因为缺省源没开long long多WA了一发。。。
希望接下来能够保持状态，少吃罚时，提升一下过题速度。
没有抽到抱枕不开心
实名羡慕一队拿到的抱枕QWQ
也希望在下一场比赛中可以拿到抱枕有更好的发挥。
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第二场
本文地址: ACM暑期集训第二场
