A.Yellow Cards
题意
题解
最少的情况就是先给两个队的每个人 $k-1$ 张，然后还剩几张就是答案。
最多的情况就是只给下场的人，同时还应该先给 $k$ 较小的队伍。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int a1,a2,k1,k2,n,ans;
signed main()
{
a1=read(); a2=read(); k1=read(); k2=read(); n=read();
printf("%d ",max(0,n-a1*(k1-1)-a2*(k2-1)));
if (k1>k2) swap(a1,a2),swap(k1,k2);
if (n/k1<=a1) ans=n/k1;
else
{
n-=a1*k1;
if (n/k2<=a2) ans=a1+n/k2;
else ans=a1+a2;
}
return !printf("%d",ans);
}B.The Number of Products
题意
题解
可以只计算一种情况的答案 $x$，另一种情况就是 $\dfrac{n\times (n+1)}{2}-x$ 。为了方便考虑正数。
对于序列 $[l,r]$ ，它的积为正数仅当 $l..r$ 有偶数个负数。所以可以按负数把数列分成多段，并对每一段用 $0/1$ 交替编号，只有编号相同的数可以组成首尾。
枚举 $r$ ，维护当前编号 $cur$ 和两种编号的数的个数，当前贡献即为编号为 $cur$ 的数的个数。注意 $r$ 是负数的话应该算到上一段，但答案需要累积另一种编号的。（以负数作为 $l,r$ 都会多一个负数）
注意开 long long
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
ll n,s[200005];
signed main()
{
n=read();
for (ll i=1;i<=n;i++) s[i]=read();
ll cnt[2]={0,0},cur=0,ans=0;
for (ll i=1;i<=n;i++)
{
cnt[cur]++;
if (s[i]<0) cur^=1;
ans+=cnt[cur];
}
return !printf("%lld %lld",1ll*n*(n+1)/2-ans,ans);
}C.Swap Letters
题意
题解
如果某种字母的个数是奇数，那么显然无解。
可以发现交换不会涉及已经相等的位，所以把它们去掉。
不相等的也就两种情况，$\begin{matrix} a \\ b \end{matrix}$ 和 $\begin{matrix} b \\ a \end{matrix}$ 。每两个相同情况的位可以用 $1$ 步变成相等的，如：
$$\begin{matrix} a \ a \\ b \ b \end{matrix} \rightarrow \begin{matrix} b \ a \\ b \ a \end{matrix}$$
令两种情况的个数为 $n,m$ ，如果均为偶数那么答案为 $\dfrac{n}{2}+\dfrac{m}{2}$ 。
否则肯定均为奇数，那么还需要两步：
$$\begin{matrix} a \ b \\ b \ a \end{matrix} \rightarrow \begin{matrix} a \ a \\ b \ b \end{matrix} \rightarrow \begin{matrix} b \ a \\ b \ a \end{matrix}$$
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=200005;
char x[N],y[N];
int n,a[N],b[N],acnt,bcnt;
signed main()
{
n=read();
scanf("%s%s",x+1,y+1);
for (int i=1;i<=n;i++)
{
if (x[i]==y[i]) continue;
if (x[i]=='a') a[++acnt]=i;
else b[++bcnt]=i;
}
if ((acnt+bcnt)&1) return 0&puts("-1");
int ans=(acnt>>1)+(bcnt>>1);
if (acnt&1 && bcnt&1) printf("%d\n",ans+2);
else printf("%d\n",ans);
for (int i=2;i<=acnt;i+=2) printf("%d %d\n",a[i],a[i-1]);
for (int i=2;i<=bcnt;i+=2) printf("%d %d\n",b[i],b[i-1]);
if (acnt&1 && bcnt&1) printf("%d %d\n%d %d\n",b[bcnt],b[bcnt],a[acnt],b[bcnt]);
return 0;
}D.Ticket Game
题意
题解
设先手为 $A$ ，后手为 $B$ 。并把数列左右两边剩下的空格个数记为 $a,b$ 。
当左右两边都有的时候，$B$ 就可以复制 $A$ 的操作。
剩下的操作中可以控制每回合的和为 $9$ ，如果刚好补完那么后手就能获得胜利，否则先手就可以阻碍后手获胜。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n;
char s[200005];
signed main()
{
n=read();
scanf("%s",s+1);
int a=0,b=0,delta=0;
for (int i=1;i<=n;i++)
{
if ((i<<1)<=n)
{
if (s[i]!='?') delta+=s[i]-'0';
else a++;
}
else
{
if (s[i]!='?') delta-=s[i]-'0';
else b++;
}
}
int cur=((a-b)>>1)*9+delta;
if (cur) return 0&puts("Monocarp");
return 0&puts("Bicarp");
}E.Marbles
这题跟 洛谷3694 很像，不过这道复杂一些。这是那道题的题解
题意
题解
状压DP，用 $f[i]$ 表示已经排好的颜色状态为 $i$ 时的最小交换次数。可以发现交换次数就是逆序对的个数。
用 $w[i][j]$ 表示有多少对 $(l,r)$ 满足：$S_l=i,S_r=j,l<r$ ，即两种颜色之间的逆序对数。
枚举当前选择的颜色 $j$ ，方程式为：
$$f[i]=\min (f[i \ xor \ 2^{j-1}] + w[j][k]) \ \ (k\in (i \ xor \ 2^{j-1}))$$
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=1<<20;
ll n,f[N],s[400005],cnt[25],w[25][25];
signed main()
{
n=read();
for (int i=1;i<=n;i++)
{
s[i]=read();
cnt[s[i]]++;
for (int j=1;j<=20;j++) w[j][s[i]]+=cnt[j];
}
memset(f,0x3f,sizeof(f)); f[0]=0;
for (int i=1;i<N;i++)
{
for (int j=0;j<20;j++) if (i>>j&1)
{
ll k=i^(1<<j),cur=0;
for (int l=0;l<20;l++) if (k>>l&1) cur+=w[j+1][l+1];
f[i]=min(f[i],f[k]+cur);
}
}
return !printf("%lld",f[N-1]);
}