此前也没有写一整场比赛题解的习惯，那就从现在开始吧。
简单的一道题，直接搜就行了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
char S[6][6];
string R,C;
int N;
void solve(int u){
if(u==N){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(S[i][j]!='.'){
if(R[i]!=S[i][j]) return;
break;
}
}
}
for(int j=0;j<N;j++){
set<char> SE;
for(int i=0;i<N;i++){
if(S[i][j]=='.') continue;
if(SE.count(S[i][j])) return;
SE.insert(S[i][j]);
}
if(si(SE)<=2) return;
for(int i=0;i<N;i++){
if(S[i][j]=='.') continue;
if(C[j]!=S[i][j]) return;
break;
}
}
cout<<"Yes\n";
for(int i=0;i<N;i++){
for(int j=0;j<N;j++) cout<<S[i][j];
cout<<"\n";
}
exit(0);
}
for(int a=0;a<N;a++){
for(int b=0;b<N;b++){
if(a==b) continue;
for(int c=0;c<N;c++){
if(a==c||b==c) continue;
if(R[u]=='A'){
if(!(a<b&&a<c)) continue;
}
if(R[u]=='B'){
if(!(b<a&&b<c)) continue;
}
if(R[u]=='C'){
if(!(c<a&&c<b)) continue;
}
S[u][a]='A';
S[u][b]='B';
S[u][c]='C';
solve(u+1);
S[u][a]='.';
S[u][b]='.';
S[u][c]='.';
}
}
}
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
cin>>N>>R>>C;
for(int i=0;i<N;i++) for(int j=0;j<N;j++) S[i][j]='.';
solve(0);
cout<<"No\n";
}
期望的题，其实也很板了，算出经过某个点的概率 $f_i$，最终答案就是所有点的工资乘上走到它的概率。
代码：
#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n, x, y, ans;
const int mod = 998244353;
int q_pow (int x, int y) {
if (y == 0) return 1;
if (y & 1) return x * q_pow (x * x % mod, y >> 1) % mod;
return q_pow (x * x % mod, y >> 1);
}
int a[300005], f[300005], g[300005];
void solve () {
cin >> n;
g[0] = 1;
For (i, 1, n) cin >> a[i];
int sum = 1;
f[0] = 1;
For (i, 1, n) {
f[i] = sum * q_pow (n, mod - 2) % mod;
sum += f[i];
sum %= mod;
}
For (i, 1, n) ans = (ans + f[i] * a[i] % mod) % mod;
cout << ans;
}
signed main () {
int _ = 1;
// cin >> _;
while (_ --) {
solve ();
cout << '\n';
}
return 0;
}
整场先看的 F，显然折半，但是 $2^{40}$ 貌似过不了，想了很多其他的东西比如 bitset。
然后才发现直接折半原来是 $2^{20}$ 的。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,y,a[88],t[88],m,d[88];
map<int,int>mp;
int slove(int v){
mp.clear();
if(m==1) return abs(t[1])==abs(v)?t[1]==-v:-1;
int k=m/2;
for(int i=0;(i>>k)==0;i++){
int s=0;
for(int j=1;j<=k;j++) s+=(i&(1<<(j-1)))?-t[j]:t[j];
mp[s]=i+1;
}
for(int i=0;(i>>m)==0;i+=(1<<k)){
int s=0;
for(int j=k+1;j<=m;j++) s+=(i&(1ll<<(j-1)))?-t[j]:t[j];
if(mp[v-s]) return i+mp[v-s]-1;
}
return -1;
}
signed main(){
cin>>n>>x>>y;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i+=2) t[++m]=a[i];
int s1=slove(y);
if(s1==-1) return puts("No"),0;
m=0;
for(int i=2;i<=n;i+=2) t[++m]=a[i];
int s2=slove(x);
if(s2==-1) return puts("No"),0;
puts("Yes");
int r=1;
for(int i=1;i<=n;i+=2) d[i]=(!!(r&s1))*2+1,r<<=1;
r=1;
for(int i=2;i<=n;i+=2) d[i]=(!!(r&s2))*2,r<<=1;
int nd=0;
for(int i=1;i<=n;i++){
putchar(d[i]==(nd+1)%4?'L':'R');
nd=d[i];
}
return 0;
}
看了几眼发现是太空飞行计划问题的原题，实际上也是如此。
对于每个技能的五个等级都建点，连向起点，等级一没有边权，剩余的边权为学习它所要花费的钱。
对于每个奖励，若他要求技能 1 要达到 4 级，就把 1 2 3 4 级的技能 1 都向他连边，边权为 inf，最后每个奖励再向终点连边，边权为奖励的钱。
然后跑最小割，这是对的，但是篇幅实在太长了，甚至于还要把最大权闭合子图拎出来，就算了，想要证明可以看看太空飞行计划问题。
数组开小调了好久，开大之后一遍过了，代码：
#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n, m, k, s, t;
int c[51], a[51], d[305], pre[305], head[305];
int l[51][51];
const int inf = 1000000000000000000;
queue <int> q;
struct Node {int u, v, w, nxt;}e[100005];
void add (int u, int v, int w) {
e[k ++] = {u, v, w, pre[u]};
pre[u] = k - 1;
}
bool BFS () {
For (i, 1, 304) head[i] = pre[i];
memset (d, 0x3f, sizeof d);
q.push (s);
d[s] = 0;
while (!q.empty () ) {
int u = q.front ();
q.pop ();
for (int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if (e[i].w && d[u] + 1 < d[v]) {
d[v] = d[u] + 1;
q.push (v);
}
}
}
return d[t] <= 600;
}
int dfs (int u, int flow) {
if (u == t || (!flow) ) return flow;
int ret = 0;
for (int &i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v, di;
if (e[i].w && d[v] == d[u] + 1 && (di = dfs (v, min (flow - ret, e[i].w) ) ) ) {
ret += di;
e[i].w -= di;
e[i ^ 1].w += di;
if (ret == flow) return ret;
}
}
return ret;
}
void solve () {
For (i, 1, 304) pre[i] = -1;
int ans = 0;
cin >> n >> m;
For (i, 1, n) cin >> c[i];
For (i, 1, m) {
cin >> a[i];
ans += a[i];
}
For (i, 1, m) For (j, 1, n) cin >> l[i][j];
s = 5 * n + m + 1;
t = 5 * n + m + 2;
For (i, 1, n) {
int x = 5 * (i - 1);
add (s, x + 1, 0);
add (x + 1, s, 0);
add (s, x + 2, c[i]);
add (x + 2, s, 0);
add (s, x + 3, c[i]);
add (x + 3, s, 0);
add (s, x + 4, c[i]);
add (x + 4, s, 0);
add (s, x + 5, c[i]);
add (x + 5, s, 0);
}
For (i, 1, m) {
add (5 * n + i, t, a[i]);
add (t, 5 * n + i, 0);
}
For (i, 1, m) {
For (j, 1, n) {
int x = 5 * (j - 1);
For (k, 1, l[i][j]) {
add (x + k, 5 * n + i, inf);
add (5 * n + i, x + k, 0);
}
}
}
while (BFS () ) {
ans -= dfs (s, inf);
}
cout << ans;
}
signed main () {
int _ = 1;
// cin >> _;
while (_ --) {
solve ();
cout << '\n';
}
return 0;
}
标签：return,int,long,ABC326,add,define,mod From： https://www.cnblogs.com/Xy-top/p/17795422.html