这是赛后做的。珍爱生命，远离edu
A.There Are Two Types Of Burgers
题意
在你的餐厅里有两种汉堡：牛肉汉堡和鸡肉汉堡。每个牛肉汉堡需要 $2$ 片面包和 $1$ 片牛肉，一个鸡肉汉堡需要 $2$ 片面包和 $1$ 个鸡排。一个牛肉汉堡卖 $h$ 元，一个鸡肉汉堡卖 $c$ 元。你有 $b$ 片面包，$p$ 片牛肉和 $f$ 块鸡排。求最大收益。
所有数据 $\le 100$ 。
题解
水题，优先卖贵的，模拟即可。
#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 t,b,p,f,h,c;
signed main()
{
t=read();
while (t--)
{
b=read(); p=read(); f=read(); h=read(); c=read();
if (h<c) swap(h,c),swap(p,f);
b>>=1;
if (b<=p) printf("%d\n",b*h);
else if (b<=p+f) printf("%d\n",p*h+(b-p)*c);
else printf("%d\n",p*h+f*c);
}
return 0;
}B.Square Filling
题意
有一个 $N\times M$ 的全零矩阵，每次可以把 $2\times 2$ 的矩阵变成 $1$ 。要求变成目标矩阵，不要求最小化步骤，求操作序列。如果无解输出 $-1$ 。
$N,M\le 50$ 。
题解
枚举所有格点，如果目标矩阵中的小矩阵全为 $1$ 就把它染了。最后如果还有没染的就无解。
#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair
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,m;
vector <pr> v;
bool s[55][55],t[55][55];
signed main()
{
n=read(); m=read();
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) t[i][j]=read();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
bool flag=1;
for (int k=i;k<=i+1;k++) for (int l=j;l<=j+1;l++) flag&=t[k][l]==1;
if (!flag) continue;
v.emplace_back(mp(i,j));
for (int k=i;k<=i+1;k++) for (int l=j;l<=j+1;l++) s[k][l]=1;
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s[i][j]!=t[i][j]) return 0&puts("-1");
printf("%lu\n",v.size());
for (auto i:v) printf("%d %d\n",i.first,i.second);
return 0;
}C.Gas Pipeline
题意
要修建一段天然气管道，高度至少为 $1$ ，如果遇到道路高度必须为 $2$ 。管道的价格为每单位 $a$ 元，柱子的价格为每单位 $b$ 元。求最小花费。
管道长度 $N\le 10^5$ ，多组数据，组数 $T\le 100$ 。
题解
用 $f[i][0/1]$ 表示当前要修第 $i$ 段管道，当前高度为 $1/2$ 时的最少花费。方程式看代码吧。
注意起点和终点的高度必须为 $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;
}
char s[200005];
ll t,n,a,b,f[200005][2];
signed main()
{
t=read();
while (t--)
{
n=read(); a=read(); b=read();
scanf("%s",s+1);
f[0][0]=b; f[0][1]=1e18;
for (ll i=1;i<=n;i++)
{
if (s[i]=='1')
{
f[i][0]=1e18;
f[i][1]=min(f[i-1][0]+((a+b)<<1)+b,f[i-1][1]+a+(b<<1));
}
else
{
f[i][0]=min(f[i-1][0]+a+b,f[i-1][1]+(a<<1)+b);
f[i][1]=min(f[i-1][0]+((a+b)<<1),f[i-1][1]+a+(b<<1));
}
}
printf("%lld\n",f[n][0]);
}
return 0;
}D.Number Of Permutations
题意
有一个长度为 $N$ 的 pair 序列。如果 first 元素单调不降，或 second 元素单调不降，就称这个序列为坏序列，否则为好序列。求序列的所有排列中好序列的个数。
$N\le 3\times 10^5$ 。
题解
根据条件没法直接算出好序列，所以考虑容斥。设 $A$ 表示 first 单调不降的序列个数；$B$ 代表 second ，则
$$ans=N^2-A-B+(A \& B)$$
考虑算 $A$ ，显然相同的数可以交换位置，设数字 $i$ 的个数为 $cnt[i]$ ，则
$$A=\prod cnt[i]!$$
$B$ 同理。
然后算 $A\& B$ 。先考虑无解的情况，按 first 为第一关键字，second 为第二关键字从小到大排序，如果存在 $second[i]>second[i+1]$ 就无解。
否则至少有 $1$ 个解，用 map 统计相同 pair 的个数，然后按照上面的f方法计算即可。
#include<bits/stdc++.h>
#define ha 998244353
#define pr pair<int,int>
#define mp make_pair
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=300005;
pr s[N];
map <pr,int> m;
int n,cnt1[N],cnt2[N],fac[N];
signed main()
{
n=read();
int mx=0; fac[0]=1;
for (int i=1;i<=n;i++)
{
s[i].first=read(); s[i].second=read();
mx=max(mx,max(s[i].first,s[i].second));
fac[i]=1ll*fac[i-1]*i%ha;
cnt1[s[i].first]++;
cnt2[s[i].second]++;
m[s[i]]++;
}
int ans1=1,ans2=1,ans3=0;
for (int i=1;i<=mx;i++)
{
if (cnt1[i]) ans1=1ll*ans1*fac[cnt1[i]]%ha;
if (cnt2[i]) ans2=1ll*ans2*fac[cnt2[i]]%ha;
}
sort(s+1,s+n+1);
for (int i=1;i<n;i++) if (s[i].second>s[i+1].second) goto output;
ans3=1;
for (auto i:m) ans3=1ll*ans3*fac[i.second]%ha;
output:
return !printf("%d",(((fac[n]-ans1+ha)%ha-ans2+ha)%ha+ans3)%ha);
}E.XOR Guessing
题意
要求猜出一个 $[0,2^{14}-1]$ 的数 $x$，可以进行两次询问，格式为
$$? \ a_1,a_2,...,a_{100}$$
程序会从中选出任意一个数，并返回 $a_i \ \mathrm{xor} \ x$ 。最后要求输出 $x$ 。
题解
构造两组数，分别使得二进制前 $7$ 位为 $0$ 、后 $7$ 位为 $0$ ，然后对返回的两个数分别取前 $7$ 位和后 $7$ 位即为答案。
#include<bits/stdc++.h>
using namespace std;
int c,d;
signed main()
{
cout<<"? ";
for (int i=1;i<=100;i++) cout<<i<<" ";
cout<<"\n";
fflush(stdout);
cin>>c;
cout<<"? ";
for (int i=1;i<=100;i++) cout<<(i<<7)<<" ";
cout<<"\n";
fflush(stdout);
cin>>d;
return !printf("! %d",(((c^d)>>7)<<7)^d);
}