A. Yogurt Sale
贪心
大概思路
两种买法，哪种最省就用哪种买，奇数情况要小判一下
参考代码
void solve(){
cin(n);cin(a);cin(b);
if(1.0*b/2>a)cout<<a*n<<et;
else cout<<(n/2)*b+(n%2)*a<<et;
}
B. Progressive Square
暴力，构造
大概思路
由题意知给定参数下的矩阵唯一，直接以元素最小值，按题意生成矩阵元素，然后暴力判是否相等即可
参考代码
void solve(){
cin(n);cin(c);cin(d);
//记录矩阵元素
vector<int>a(n*n),b;
CV(a);
sort(a.begin(),a.end());
//暴力生成元素
rep(i,0,n-1)rep(j,0,n-1)b.push_back(a[0]+i*c+j*d);
sort(b.begin(),b.end());
ANS(a==b);
}
C. Inhabitant of the Deep Sea
暴力，模拟
大概思路
直接取一半，两边往中间暴力删数即可
参考代码
void solve(){
cin(n);cin(k);
vector<ll>a(n);
CV(a);
ll sum=0;
for(auto &i:a)sum+=i;
if(k>=sum){cout<<n<<et;return;}
ll l=k/2+k%2;
ll r=k/2;
int cnt=0;
rep(i,0,n-1){
if(l<a[i]){a[i]-=l;break;}
l-=a[i];a[i]=0;cnt++;
}
rrep(i,n-1,0){
if(r<a[i])break;
r-=a[i];cnt++;
}
cout<<cnt<<et;
}
D. Inaccurate Subsequence Search
滑动窗口
大概思路
用小的数组在大数组上滑动统计答案即可，开个map桶记录出现的数个数
参考代码
void solve(){
cin(n);cin(m);cin(k);
vector<int>a(n);
CV(a);
map<int,int> cnt,acnt;
rep(i,1,m){//记录小数组（匹配用）的各元素出现次数
cin(tmp);
cnt[tmp]++;
}
ll ans=0;
rep(i,0,m-1){//将小数组与大数组左端对其，收集子数组出现的元素个数
acnt[a[i]]++;
}
ll same=0;//先暴力统计一遍匹配的数，准备开始滑动
for(auto &[i,v]:acnt){
if(acnt[i]&&cnt[i])same+=min(acnt[i],cnt[i]);
}
if(same>=k)ans++;
rep(i,m,n-1){//开始滑动，边滑动边收集
if(acnt[a[i-m]]<=cnt[a[i-m]])same--;
acnt[a[i-m]]--;
if(acnt[a[i]]<cnt[a[i]])same++;
acnt[a[i]]++;
if(same>=k)ans++;
}
cout<<ans<<et;
}
E. Long Inversions
贪心，差分
大概思路
会的人一下子就想出来了，不会的怎么想都想不出来
从左到右贪心，比方说1011101这个样例，设k=4，如果只对某一位取反，必然会影响到第i+k位的数，在k等于4时，是否该取反的状态如下：
第1到第4个数：0100 第5到第7个数：010
此时按位异或，会发现他们均为0
- 对样例0100010，取k=4时，取反状态如下：
[1~4]：1011 [5~7]：101
按位异或不全为0，故k不可能取4；取k=3时，有：
[1~3]：101 [4~6]：110 [7~7]：1
按位异或全为1，其一种推导路径如下：
0100010 0111110 1001110 1001001 1110001 1111111
因此我们只需要开个差分数组，暴力从大到小枚举k，找到使差分数组值全相等时的情况输出即可（k=1必然可行，不用担心边界）
参考代码
void solve(){
cin(k);scin(s);
do{
vector<int>a(k);
rep(i,0,s.length()-1)a[i%k]^='1'-s[i];
if(a==vector<int>(k,a[0])){cout<<k<<et;return;}
}while(k--);
}
F. Unfair Game
位运算，结论题
大概思路
水题，把1,2,3,4二进制状态全列出来如下：
001 010 011 100
很容易发现1^2^3=0的结论，又因为偶数个相同的数异或起来为0，所以设1，2，3，4的个数分别为a，b，c，d的话，答案就是a/2+b/2+c/2+d/2，当a，b，c均为奇数时，答案要加1
参考代码
void solve(){
cin(a);cin(b);cin(c);cin(d);
cout<<a/2+b/2+c/2+d/2+(a%2&&b%2&&c%2)<<et;
}
G. GCD on a grid
因数，bfs，可行性DP（感觉能用可行性dp的，一般也能bfs）
大概思路
hack期最有趣的一题，有人拿了逆天数据hack掉了300多号人，排名第一页全军覆没，还好赛后重测时又重测了（不对，我又没ac，我管这么多干嘛）
从2到 $\gcd(a[0][0],a[n][m])$ 枚举因子，然后跑bfs或dp即可（似曾相识的思路）
题外话，开vector跑了1000ms，开全局数组只跑了500ms，快了一倍
参考代码
void solve() {
cin(n);cin(m);
vectors<2>a(n,vector<int>(m)),dp(n,vector<int>(m));
rep(i,0,n-1)rep(j,0,m-1)cin>>a[i][j];
auto ck=[&](int d){
dp.assign(n, vector<int>(m, 0));
rep(i,0,n-1)rep(j,0,m-1)dp[i][j]=0;
dp[0][0]=1;//可行性dp
rep(i,0,n-1)rep(j,0,m-1)if(a[i][j]%d==0) {
if(i)dp[i][j]|=dp[i-1][j];//可行性传递
if(j)dp[i][j]|=dp[i][j-1];
}
return dp[n-1][m-1];
};
int qwq=__gcd(a[0][0],a[n-1][m-1]),ans=1;
for(int d=1;d<=qwq/d;d++){
if(qwq%d==0){
if(ck(d))ans=max(ans,d);
if(ck(qwq/d)){ans=max(ans,qwq/d);break;}
}
}
CA;
}
H. The Most Reckless Defense
费用流，MCFC，状压dp
大概思路
没学过费用流和MCFC，这里只看了状压dp的思路
题意说，每个半径只能使用一次，怪的血量又与半径有关系，这个关系式中含指数，半径每增大1，可对怪造成的最大影响就增大 $\Delta D= (r^2-(r-1)^2)\times 500$，但是怪的额外血量会提高 $\Delta H=3^r-3^{r-1}$，算一下会发现，当 $r=10$ 时，$\Delta H>\Delta D$，因此半径再继续增加是没有意义的。
所以我们设10个状态位，表示1到10的半径使用情况，做状压dp。设$dp[S]$ 表示半径选择状态为 S 时，可以设置的最大基础血量，然后每读入一个防御塔信息后，枚举状态，枚举该防御塔的半径，更新各个状态的最优值，最后输出 $dp[(1«10)-1]$ 这个状态即可（半径全用上肯定是最优的）。
参考代码
void solve() {
ll n,m,k;cin>>n>>m>>k;
string s[n+1];
rep(i,1,n){cin>>s[i];s[i]=" "+s[i];}
vector<int> dp(1<<10),dp_(1<<10);
while(k--){
ll x,y,p;cin>>x>>y>>p;
ll cnt[11]={0};//统计该塔在半径设为r时，可影响到的格子数
rep(i,1,n)rep(j,1,m)if(s[i][j]=='#'){
int r=ceil(hypot(x-i,y-j));
if(r<=10)cnt[r]++;
}
rep(i,1,10)cnt[i]+=cnt[i-1];
dp_=dp;//滚动一下
rep(I,0,(1<<10)-1){//枚举所有状态
int w=1;
rep(j,1,10){//枚举该塔取各个半径r时，当前状态是否可以有更优的答案
w*=3;
if(I>>j-1&1)dp[I]=max(dp[I],dp_[I^1<<j-1]+cnt[j]*p-w);
}
}
}
cout<<dp[(1<<10)-1]<<et;
}
附录
这里贴上用到的头部和main函数(有更新，更了奇怪的类模版递推以简化嵌套vector的写法)：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
namespace Xiaoxia{
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#define et '\n'
#define reg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rrep(i,a,b) for(int i=(a);i>=(b);i--)
#define cin(a) ll a;cin>>a
#define dcin(a) ld a;cin>>a
#define scin(a) string a;cin>>a
#define CA cout<<ans<<et
#define CY cout<<"YES"<<et
#define CN cout<<"NO"<<et
#define max(a,b) ((a>b)?(a):(b))
#define min(a,b) ((a<b)?(a):(b))
#define CV(x) for(auto &i:x)cin>>i
template<int n,typename T>struct VEC_ {
using type=vector<typename VEC_<n-1,T>::type>;
};
template<typename T>struct VEC_<1,T> {
using type=std::vector<T>;
};
template <int n=1,typename T=int>
using vectors = typename VEC_<n, T>::type;
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
int M = 1e9 + 7;
inline ll MO(ll x){return (x%M+M)%M;}
inline void ANS(bool x){cout<<(x?"Yes\n":"No\n");}
}
using namespace Xiaoxia;
void solve(){
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//pre();
cin(t);while(t--)
solve();
return 0;
}