CF1195A Drinks Choosing
先将相同权值的配对直到只剩下一个，然后再配剩下的单个。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
int n,k;
int a[N];
int cnt[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++)
cnt[a[i]]++;
int ans=0,ret=(n+1)/2;
for(int i=1;i<=k;i++)
{
int num=min(cnt[i]/2,ret);
ans+=num*2,ret-=num,cnt[i]-=num*2;
}
if(ret>0)
{
for(int i=1;i<=k;i++)
if(cnt[i]>0&&ret>0) ans++,ret--,cnt[i]--;
}
printf("%d",ans);
return 0;
}
CF1195B Sport Mafia
设总共放入 \(x\) 次，则有：
\[\frac{x(x+1)}{2}-(n-x)=k
\]
解得 \(x=\frac{-3+\sqrt{4(2n+2k)+9}}{2}\)。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,k;
int main()
{
scanf("%lld%lld",&n,&k);
printf("%lld",n-(-3+((long long)sqrt(4*(2*n+2*k)+9)))/2);
return 0;
}
CF1195C Basketball Exercise
令 \(f_{i,0/1/2}\) 表示第 \(i\) 行没有选，选了第一行，选了第二行的最大和。直接转移就好了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[3][N];
long long f[N][4];
int main()
{
scanf("%d",&n);
for(int i=1;i<=2;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
{
f[i][0]=max({f[i-1][0],f[i-1][1],f[i-1][2]});
f[i][1]=max({f[i-1][0],f[i-1][2]})+a[1][i];
f[i][2]=max({f[i-1][0],f[i-1][1]})+a[2][i];
}
long long ans=max({f[n][0],f[n][1],f[n][2]});
printf("%lld",ans);
return 0;
}
CF1195D Submarine in the Rybinsk Sea
考虑 \(a_i\) 的位数相等怎么做，可以发现，我们可以对于每个 \(a_i\) 的每一位分别计算贡献。
\(a_i\) 的位数不同时只需要枚举与 \(a_i\) 配对的另一个数的位数 \(j\)，然后算出贡献乘上位数为 \(j\) 的数的个数即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
const int MOD=998244353;
int n;
int a[N];
int cnt[20];
int count(int x)
{
int cnt=0;
while(x)
x/=10,cnt++;
return cnt;
}
long long calc1(int x,int tot)
{
static int b[100];
int l=0;
long long res=0;
while(x)
{
b[++l]=x%10,x/=10;
if(tot) b[++l]=0,tot--;
}
for(int i=l;i>=1;i--)
res=(res*10+b[i])%MOD;
return res;
}
long long calc2(int x,int tot)
{
static int b[100];
int l=0;
long long res=0;
while(x)
{
if(tot) b[++l]=0,tot--;
b[++l]=x%10;
x/=10;
}
for(int i=l;i>=1;i--)
res=(res*10+b[i])%MOD;
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),cnt[count(a[i])]++;
long long ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=9;j++)
ans=(ans+calc1(a[i],j)*cnt[j]%MOD+calc2(a[i],j)*cnt[j]%MOD)%MOD;
printf("%lld",ans);
return 0;
}
CF1195E OpenStreetMap
可以先用单调队列预处理出 \(pre_{i,j}\) 表示 \((i,j-b+1)\sim (i,j)\) 的最小值。
然后枚举当前列，然后依次加入每行的 \(pre\)，就可以用单调队列快速求出一个位置的矩形最小值。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=3005;
int n,m,a,b;
long long g[N*N];
int x,y,z;
int h[N][N];
int pre[N][N];
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
scanf("%d%d%d%d",&g[0],&x,&y,&z);
for(int i=1;i<=n*m;i++)
g[i]=(g[i-1]*x+y)%z;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
h[i][j]=g[(i-1)*m+j-1];
for(int i=1;i<=n;i++)
{
deque<int>q;
for(int j=1;j<=m;j++)
{
while(!q.empty()&&j-q.front()+1>b) q.pop_front();
while(!q.empty()&&h[i][q.back()]>=h[i][j]) q.pop_back();
q.push_back(j);
pre[i][j]=h[i][q.front()];
}
}
long long ans=0;
for(int j=b;j<=m;j++)
{
deque<int>q;
for(int i=1;i<=n;i++)
{
while(!q.empty()&&i-q.front()+1>a) q.pop_front();
while(!q.empty()&&pre[q.back()][j]>=pre[i][j]) q.pop_back();
q.push_back(i);
if(i>=a) ans+=pre[q.front()][j];
}
}
printf("%lld",ans);
return 0;
}
CF1195F Geometers Anonymous Club
问题等价于求 \(l\sim r\) 的凸包上有多少斜率不同或方向不同的向量。
就是问一个区间有多少不同的颜色，离线后树状数组搞一搞就可以了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=300005;
int n,m,Q;
int c[N];
struct Node
{
int l,r,id;
}ask[N];
int book[N];
int res[N];
struct BIT
{
int C[N];
int lowbit(int x)
{
return x&-x;
}
void add(int x,int y)
{
for(int i=x;i<=m;i+=lowbit(i))
C[i]+=y;
return;
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=C[i];
return ans;
}
}T;
int st[N],ed[N];
pair<int,int> a[N];
int tot;
pair<int,int> b[N];
pair<int,int> slope(int x1,int y1,int x2,int y2)
{
int x=x2-x1,y=y2-y1;
int g=abs(__gcd(x,y));
return make_pair(x/g,y/g);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
st[i]=m;
static int x[N],y[N];
for(int j=1;j<=k;j++)
scanf("%d%d",&x[j],&y[j]);
for(int j=2;j<=k;j++)
a[++m]=slope(x[j-1],y[j-1],x[j],y[j]),b[++tot]=a[m];
a[++m]=slope(x[k],y[k],x[1],y[1]),b[++tot]=a[m];
ed[i]=m;
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=m;i++)
c[i]=lower_bound(b+1,b+tot+1,a[i])-b;
scanf("%d",&Q);
for(int i=1;i<=Q;i++)
{
scanf("%d%d",&ask[i].l,&ask[i].r);
ask[i].l=st[ask[i].l]+1,ask[i].r=ed[ask[i].r];
ask[i].id=i;
}
sort(ask+1,ask+Q+1,[=](const Node &x,const Node &y){return x.r<y.r;});
for(int i=1,j=1;i<=Q;i++)
{
while(j<=ask[i].r)
{
if(book[c[j]]) T.add(book[c[j]],-1);
T.add(j,1);
book[c[j]]=j;
j++;
}
res[ask[i].id]=T.getsum(ask[i].r)-T.getsum(ask[i].l-1);
}
for(int i=1;i<=Q;i++)
printf("%d\n",res[i]);
return 0;
}