A
按题意直接模拟即可。也就是每次取出一些字符，放入字符串\(P\)中。
注意实现时的时间复杂度，不要写成 \(O(n^2)\) 的。
#include<bits/stdc++.h>
using namespace std;
char s[1000010],t[1000010];
int hd1=1,hd2=1,n,m,x,y;
char ans[2000010];
int main()
{
scanf("%s",s+1);n=strlen(s+1);
scanf("%s",t+1);m=strlen(t+1);
scanf("%d%d",&x,&y);
while(hd1<=n||hd2<=m)
{
for(int i=1;hd1<=n&&i<=x;i++)
putchar(s[hd1++]);
for(int i=1;hd2<=m&&i<=y;i++)
putchar(t[hd2++]);
}
}
B
发现一定是小羊优先匹配小牛，小牛匹配小羊，并且今日准备饼干数量多的店主优先匹配，最后可能还会剩下一些无法匹配的店主。
可以先分类再排序，然后贪心选择就可以取到最大值。
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct item
{
int tp,val;
};
item a[100010];
long long ans=0;
bool cmp(item x,item y)
{
if(x.tp!=y.tp)
return x.tp<y.tp;
return x.val>y.val;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].tp,&a[i].val);
sort(a+1,a+n+1,cmp);
int c0=m,c1=n-m;
for(int i=1;i<=n;i++)
{
if(a[i].tp==1)
{
if(c0>0)
c0--,ans+=a[i].val*2;
else
c1--,ans+=a[i].val;
}
else
{
if(c1>0)
c1--,ans+=a[i].val*1.5;
else
c0--,ans+=a[i].val;
}
}
printf("%lld\n",ans);
}
C
考虑 \(C_{i,j}\) 和 \(C_{i,j+1}\) 的差为 \(|A_i+B_j-A_i-B_{j+1}|\) ，也就是 \(|B_j-B_{j+1}|\) ，\(C_{i+1,j}\) 同理。
由此可发现，走回头路一定不优，且所有只向右和向下的方案代价都一样，所以答案就是 \(\sum_{i=1}^{n-1}|A_i-A_{i+1}|+\sum_{i=1}^{m-1}|B_i-B_{i+1}|\)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000010], b[1000010];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
long long sum = 0;
for (int i = 2; i <= n; i++) sum += abs(a[i] - a[i - 1]);
for (int i = 2; i <= m; i++) sum += abs(b[i] - b[i - 1]);
printf("%lld\n", sum);
}
D
考虑记录每个士兵是否得到了军令。
将所有时间按照时间顺序排序后，按时间顺序模拟所有事件的发生即可，即如果两个士兵中有一个得到了消息，则记录下另一个士兵得到消息的信息。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int t;
bool vis[1000010];
struct event
{
int x,y;
double ti;
};
bool cmp(event x,event y)
{
return x.ti<y.ti;
}
event p[500010];
int cnt=0;
int a[100010],b[100010];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
vis[i]=0;
cnt=0;
vis[m]=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(a[i]==a[j])
p[++cnt]=(event){i,j,0};
else if(b[i]!=b[j]&&(a[i]>a[j])!=(b[i]>b[j]))
p[++cnt]=(event){i,j,1.0*(a[i]-a[j])/(b[j]-b[i])};
}
sort(p+1,p+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
vis[p[i].x]|=vis[p[i].y]|=vis[p[i].x];
int ans=0;
for(int i=1;i<=n;i++)
ans+=vis[i];
printf("%d\n",ans);
}
}
E
考虑每一位的贡献是独立的, 那么可以分别对每一位做。
从左到右扫一遍, 对每一位维护两个值, 分别表示当前总共有多少个 \(1\) , 当前异或起来总共有多少个 \(1\) , 即维护了 \(a_i\) 以及 \(a_i \oplus a_j\) 。
可能稍微有点卡常, 可以参考 std。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n, k;
ull a[4000005], ans, U, seed;
int main() {
scanf("%d%llu%d", &n, &seed, &k);
srand(seed);
U = (k == 64 ? 0ull : (1ull << k)) - 1ull;
mt19937_64 rnd(seed);
for(int i = 1; i <= n; i++) a[i] = rnd() & U;
ull ans = 0;
for(int i = 0; i < k; i++) {
ull cnt0 = 0, cnt1 = 0, t = 0, res = 0;
for(int j = 1; j <= n; j++) {
bool fl = (a[j] >> i) & 1;
res += fl * 1ull * (j - 2) * (j - 1) / 2 + (!fl) * t, cnt1 += fl, cnt0 += !fl, t += fl * cnt0 + (!fl) * cnt1;
}
ans += res * (1ull << i);
}
printf("%llu\n", ans);
return 0;
}