CF1079A Kitchen Utensils
令 \(c_i\) 表示餐具 \(i\) 出现的数量，最小的餐具套数为 \(t=\lceil \frac{\max\{c_i\}}{k}\rceil\)，按照这个计算就好了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105;
int n,k;
int a[N];
int c[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
c[a[i]]++;
int m=0;
int cnt=0;
for(int i=1;i<=100;i++)
{
m=max(m,c[i]);
if(c[i]>0) cnt++;
}
m=(m+k-1)/k*k;
printf("%d",m*cnt-n);
return 0;
}
CF1079B Personalized Cup
最小行数即为 \(\lceil \frac{n}{20}\rceil\)，算出对应列数直接瞎 jb 输出。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int n;
int a,b;
char s[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
a=(n+20-1)/20;
if(n%a==0)
{
b=n/a;
printf("%d %d\n",a,b);
int now=0;
for(int i=1;i<=a;i++)
{
for(int j=1;j<=b;j++)
printf("%c",s[++now]);
printf("\n");
}
return 0;
}
b=n/a+1;
printf("%d %d\n",a,b);
int cnt=0;
bool flag=false;
for(int i=1;i<=a;i++)
{
if(!flag&&(n-cnt)%(b-1)==0) b--,flag=true;
for(int j=1;j<=b;j++)
printf("%c",s[++cnt]);
if(flag) printf("*");
printf("\n");
}
return 0;
}
CF1079C Playing Piano
令 \(f_{i,0/1/2/3/4/5}\) 表示考虑前 \(i\) 个位置，\(a_i=0/1/2/3/4/5\) 时是否合法，然后直接转移即可，方案很好输出就不写了。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N];
bool f[N][6];
vector<int>res;
void print(int n,int x)
{
if(n==1)
{
res.emplace_back(x);
return ;
}
res.emplace_back(x);
if(a[n]>a[n-1])
{
for(int y=1;y<x;y++)
if(f[n-1][y]) return print(n-1,y);
}
if(a[n]<a[n-1])
{
for(int y=x+1;y<=5;y++)
if(f[n-1][y]) return print(n-1,y);
}
if(a[n]==a[n-1])
{
for(int y=1;y<=5;y++)
if(y!=x&&f[n-1][y]) return print(n-1,y);
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int x=1;x<=5;x++)
f[1][x]=true;
for(int i=2;i<=n;i++)
{
if(a[i]>a[i-1])
{
for(int x=1,flag=0;x<=5;x++) f[i][x]=flag,flag|=f[i-1][x];
}
else if(a[i]<a[i-1])
{
for(int x=5,flag=0;x>=1;x--) f[i][x]=flag,flag|=f[i-1][x];
}
else if(a[i]==a[i-1])
{
int cnt=0;
for(int x=1;x<=5;x++) cnt+=f[i-1][x];
for(int x=1;x<=5;x++) f[i][x]=(cnt-f[i-1][x])>0;
}
}
for(int i=1;i<=5;i++)
if(f[n][i])
{
print(n,i);
reverse(res.begin(),res.end());
for(int u:res)
printf("%d ",u);
return 0;
}
printf("-1");
return 0;
}
CF1079D Barcelonian Distance
找出直线的四个交点，然后在走直线和不走之间取个 \(\min\) 就好了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int a,b,c;
struct Point
{
double x,y;
Point(double _x=0,double _y=0)
{
x=_x,y=_y;
return;
}
bool operator<(const Point &b)const
{
return x<b.x||(x==b.x&&y<b.y);
}
bool operator==(const Point &b)const
{
return x==b.x&&y==b.y;
}
};
double calcx(double a,double b,double c,double y)
{
return (-b*y-c)/a;
}
double calcy(double a,double b,double c,double x)
{
return (-a*x-c)/b;
}
double dis(Point a,Point b)
{
return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x));
}
int main()
{
scanf("%d%d%d",&a,&b,&c);
Point A,B;
scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
double x1=calcx(a,b,c,A.y),x2=calcx(a,b,c,B.y),y1=calcy(a,b,c,A.x),y2=calcy(a,b,c,B.x);
vector<Point>pos;
if(min(A.x,B.x)<=x1&&x1<=max(A.x,B.x)) pos.emplace_back(x1,A.y);
if(min(A.x,B.x)<=x2&&x2<=max(A.x,B.x)) pos.emplace_back(x2,B.y);
if(min(A.y,B.y)<=y1&&y1<=max(A.y,B.y)) pos.emplace_back(A.x,y1);
if(min(A.y,B.y)<=y2&&y2<=max(A.y,B.y)) pos.emplace_back(B.x,y2);
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
double ans=abs(A.x-B.x)+abs(A.y-B.y);
for(Point x:pos)
for(Point y:pos)
{
if((A.x==x.x||A.y==x.y)&&(B.x==y.x||B.y==y.y)) ans=min(ans,dis(A,x)+dis(x,y)+dis(y,B));
}
printf("%.7lf",ans);
return 0;
}
CF1079E The Unbearable Lightness of Weights
可以发现，我们肯定确定下质量相同的一些砝码，我们相当于要找到最多的相同砝码使得它们不能被相同数量的其他砝码表示出来。
直接分别对于某种质量的砝码 DP 是 \(O(n^5)\) 的。
变化一下思路，我们可以去计算方案数，令 \(f_{i,j,k}\) 表示考虑前 \(i\) 个砝码，用 \(j\) 个砝码表示出质量 \(k\) 的方案数。对于质量 \(w\) 的砝码取出 \(t\) 个合法的条件为 \(f_{n,w\cdot t,t}=C_{c_w}^t\)，\(c_w\) 表示质量为 \(w\) 的砝码数量。
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int N=105;
map<pair<int,int>,int>dp,pre;
int n;
int a[N],cnt[N];
int C[N][N];
int main()
{
scanf("%d",&n);
int tot=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(cnt[a[i]]==0) tot++;
cnt[a[i]]++;
}
int m=*max_element(a+1,a+n+1);
if(tot<=2)
{
printf("%d",n);
return 0;
}
for(int i=0;i<=n;i++)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<=i;j++)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
dp[{0,0}]=pre[{0,0}]=1;
for(int i=1;i<=n;i++)
{
for(auto [v,s]:pre)
dp[{v.first+a[i],v.second+1}]+=s;
pre=dp;
}
int ans=1;
for(int w=1;w<=m;w++)
for(int i=2;i<=cnt[w];i++)
if(dp[{w*i,i}]==C[cnt[w]][i]) ans=max(ans,i);
printf("%d",ans);
return 0;
}
CF1079F Vasya and Maximum Matching
对于一个点，要么跟父亲匹配，要么跟儿子匹配，要么不匹配。
令 \(f_{u,0/1/2}\) 表示考虑 \(u\) 的子树中的点，\(u\) 不匹配/跟父亲匹配/跟儿子匹配的方案数，转移为：
\[f_{u,0}=\prod_{v\in\operatorname{son}(u)}(f_{v,0}+f_{v,2}) \]\[f_{u,1}=\prod_{v\in\operatorname{son}(u)}(f_{v,0}+2f_{v,2}) \]\[f_{u,2}=\prod_{v\in\operatorname{son}(u)}\left(\prod_{x\in\operatorname{son}(u), \atop x\neq v}(f_{x,0}+2f_{x,2})\right)f_{v,1} \]#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=300005;
const int MOD=998244353;
int n;
vector<int>G[N];
long long f[N][3];
long long ksm(long long a,long long b)
{
long long res=1;
while(b)
{
if(b&1) res=res*a%MOD;
a=a*a%MOD,b>>=1;
}
return res;
}
void dfs(int u,int father)
{
f[u][0]=f[u][1]=1;
f[u][2]=0;
long long sum=1;
for(int v:G[u])
{
if(v==father) continue;
dfs(v,u);
f[u][0]=f[u][0]*(f[v][0]+f[v][2])%MOD;
f[u][1]=f[u][1]*(f[v][0]+f[v][2]*2)%MOD;
sum=sum*(2*f[v][2]+f[v][0])%MOD;
}
for(int v:G[u])
{
if(v==father) continue;
f[u][2]=(f[u][2]+sum*ksm(2*f[v][2]%MOD+f[v][0],MOD-2)%MOD*f[v][1])%MOD;
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x].emplace_back(y);
G[y].emplace_back(x);
}
dfs(1,0);
printf("%lld",(f[1][0]+f[1][2])%MOD);
return 0;
}
CF1079G Chattering
对于一个点 \(i\)，它能跳到的区间为 \([i-a_i,i+a_i]\)。对于某个时刻，能跳到的位置一定是一个区间。
有一个暴力的想法就是暴力维护每次的区间，然后一步步跳直到区间长度 \(\ge n\)，时间复杂度 \(O(n^2)\)。
考虑倍增，令 \(L_{i,j}\) 表示从 \(i\) 开始，走 \(2^j\) 步能到的左端点，\(R_{i,j}\) 表示从 \(i\) 开始，走 \(2^j\) 步能到的右端点，转移为：
\[L_{i,j}=\min_{L_{i,j-1}\leq t\leq R_{i,j-1}}\{L_{t,j-1}\} \]\[R_{i,j}=\max_{L_{i,j-1}\leq t\leq R_{i,j-1}}\{R_{t,j-1}\} \]直接倍增跳就完了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=300005;
int n;
int a[N];
int Lg[N];
int L[N][22],R[N][22];
struct Segment_Tree
{
struct Node
{
int Min,Max;
}tree[N<<2];
void push_up(int i)
{
if(!i) return;
tree[i].Min=min(tree[i*2].Min,tree[i*2+1].Min);
tree[i].Max=max(tree[i*2].Max,tree[i*2+1].Max);
return;
}
void build(int i,int l,int r,int k)
{
if(l==r)
{
tree[i].Min=L[l][k];
tree[i].Max=R[l][k];
return;
}
int mid=(l+r)/2;
build(i*2,l,mid,k);
build(i*2+1,mid+1,r,k);
push_up(i);
return;
}
Node query(int i,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return {tree[i].Min,tree[i].Max};
int mid=(l+r)/2;
if(R<=mid) return query(i*2,l,mid,L,R);
else if(L>mid) return query(i*2+1,mid+1,r,L,R);
else
{
Node a=query(i*2,l,mid,L,R),b=query(i*2+1,mid+1,r,L,R);
return {min(a.Min,b.Min),max(a.Max,b.Max)};
}
}
}T[22];
int solve(int u)
{
int l=u,r=u;
int tot=0;
for(int j=Lg[n*3];j>=0;j--)
{
Segment_Tree::Node nxt= T[j].query(1,1,3*n,l,r);
int nl=nxt.Min,nr=nxt.Max;
if(nr-nl+1<n)
{
l=nl,r=nr;
tot+=1<<j;
}
}
return tot+1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
if(n==1)
{
printf("0");
return 0;
}
Lg[0]=1;
for(int i=1;i<=n*3;i++)
Lg[i]=Lg[i/2]+1;
for(int i=1;i<=n;i++)
a[i+n+n]=a[i+n]=a[i];
for(int i=1;i<=n*3;i++)
L[i][0]=max(i-a[i],1),R[i][0]=min(i+a[i],n*3);
T[0].build(1,1,3*n,0);
for(int k=1;k<=Lg[n*3];k++)
{
for(int i=1;i<=n*3;i++)
{
Segment_Tree::Node nxt=T[k-1].query(1,1,3*n,L[i][k-1],R[i][k-1]);
L[i][k]=nxt.Min,R[i][k]=nxt.Max;
}
T[k].build(1,1,3*n,k);
}
for(int i=1;i<=n;i++)
printf("%d ",solve(i+n));
return 0;
}