https://codeforces.com/gym/102566
A
有一个起点、一个终点，给出 \(m\) 列不同车次的列车始发站和终点站，你只能从中选择一部分列车，使得它们不会在除了起点和终点外的任何地方相遇
网络流板子题。
点击查看代码
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 409;
ll pre[maxn],gap[maxn],h[maxn];//pre��¼�Ǵ���һ���ߵ���i�ģ�gap��¼��i�����м����㣬h��¼i��IJ�Ρ�
ll firs[maxn];//�ڽӱ���
struct node{
ll v,flow,nex;
}edge[maxn*maxn];
int N, n, m, S, T;
inline int in(int x) {
return x;
}
inline int out(int x) {
return x + n + 1;
}
void build_edge(int u,int v,int flow){
edge[N]=(node){v,flow,firs[u]};
firs[u]=N++;
edge[N]=(node){u,0,firs[v]};
firs[v]=N++;
}
void bfs(int s,int t)//���ѽ��㣬���������Ǵӻ�㿪ʼ�ģ���Ū���ˣ�
{
//��ʼ��
memset(h,-1,sizeof(h));
memset(gap,0,sizeof(gap));
queue<int>q;
while(!q.empty())q.pop();
q.push(t);
h[t]=0;//����㶨��Ϊ0��
gap[0]=1;//0���ĸ�����һ
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=firs[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].v;
if(h[v]==-1)
{
h[v]=h[u]+1;
gap[h[v]]++;//��¼��ǰ��ĸ���
q.push(v);
}
}
}
}
ll isap(int s,int t,int n){
bfs(s,t);
memset(pre,0,sizeof(pre));//��¼�õ��ǰ����˭�������ǰ����ָ�ߣ����ǵ㣩
ll ans=0,d,u=s;//ans��¼�����,d��¼��ǰ·���е���С��,u��¼��ǰ���ҵ��ĸ����ˡ�
while(h[s]<n)//���Դ��IJ�С�ڵ�ĸ����Ϳ��ܻ�����
{
int flag=1;//�ж��Ƿ��ܹ��ߣ��ܷ��ҵ�����
if(u==s) d=inf;//����ٴδ�Դ��������ͳ�ʼ��d��
for(int i=firs[u];i!=-1;i=edge[i].nex)
{
ll v=edge[i].v,flow=edge[i].flow;
if(h[v]+1==h[u]&&flow)
{
pre[v]=i;//��¼�õ����������ߵ����
u=v;//��¼Ҫȥ�ĸ���
d=min(d,flow);//��¼��С��
flag=0;//�ܹ���ǰ��
if(v==t)//����ߵ��˻��
{
while(u!=s)//ԭ·���أ����±ߵ���������dinic��dfs˼·һ��
{
int j=pre[u];
edge[j].flow-=d;
edge[j^1].flow+=d;
u=edge[j^1].v;
}
ans+=d;
}
break;
}
}
if(flag)
{
if(--gap[h[u]]==0) //����ò���û���˵㣬˵��û�����������ˣ�������
break;
ll min_=n-1;
for(int i=firs[u];i!=-1;i=edge[i].nex)//������u��������С�㣬
{
ll v=edge[i].v,flow=edge[i].flow;
if(flow)
min_=min(min_,h[v]);
}
h[u]=min_+1;//���¸�u����
gap[h[u]]++;//���²�ĸ���
if(u!=s)//��Ҫһ���������ǰ�㲻��Դ���Ҫ�����һ�����������ҡ�
u=edge[pre[u]^1].v;
}
}
return ans;
}
int main(){
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d",&n,&m);
memset(firs,-1,sizeof(firs));
N=0;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
build_edge(out(u), in(v), 1);
}
for(int i = 0; i <= n; i++) {
build_edge(in(i), out(i), 1);
}
S = out(0);
T = in(n);
n = n * 2 + 2;
printf("%lld\n",isap(S,T,n));
}
return 0;
}
C
需要求出一个序列的最长不下降子序列的长度，以及包含任意 最长不下降的子序列的 长度最短的区间
记录长度只需要在基础LIS的算法上另外存一下位置信息。
点击查看代码
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e5 + 100;
int t, n, m, x;
int a[N], b[N], tem[N], pos[N];
int len;
vector<int> v[N];
// ?????????????
// ????????????????????????????????
void solve() {
len = 0;
b[++len] = a[1];
pos[1] = 1;
v[1].push_back(1);
for(int i = 2; i <= n; i++) {
if(a[i] >= b[len]) {
b[++len] = a[i];
pos[i] = len;
}
else {
int id = upper_bound(b + 1, b + len + 1, a[i]) - b;
b[id] = a[i];
pos[i] = id;
}
// cout << i <<' '<<a[i]<<' '<<pos[i]<<endl;
v[pos[i]].push_back(i);
}
printf("%d ", len);
int ans = 1e9;
for(auto i : v[len]) { // i :
int pos = i;
for(int j = len - 1; j >= 1; j--) {
int p = lower_bound(v[j].begin(), v[j].end(), pos) - v[j].begin();
p -= 1;
pos = v[j][p];
}
ans = min(ans, i - pos + 1);
}
printf("%d\n", ans - len);
}
int main(){
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
v[i].clear();
}
solve();
}
system("pause");
return 0;
}
D
折半搜索（meet in the middle）
先计算前一半东西，并把结果存储下来（每个结果都是一个三十维向量，可以map存也可以哈希一下），在计算后一半东西的时候同时判断
注：
__builtin_popcount(S)计算 \(S\) 的二进制表示中 1 的个数
__builtin_popcount = int
__builtin_popcountl = long int
__builtin_popcountll = long long
- 存储一个序列的信息的方法：
map<vector<int>, int>- 哈希。（整数的哈希可看作转化成MAX进制下的表示
- trie树
- unordered_map 和 map 的区别：
unordered_map内部实现是哈希表，需要键是可以哈希的，一般为基础数据类型
map内部实现是红黑树，只要能做比较的数据类型（例如vector、pair）都是可以的
点击查看代码
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 33, seed = 1501;
int t, n, m;
int b[N], x[N][N], y[N][N];
int val[N];
map<vector<int>, int> mp;
int main(){
int t; cin >> t;
while (t--) {
mp.clear();
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
for(int i = 0; i < n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d%d", &x[i][j], &y[i][j]);
}
}
int nn = n / 2;
int ans = 100;
for(int S = 0; S < (1 << nn); S++) {
for(int j = 1; j <= m; j++) {
int va = 0;
for(int i = 0; i < nn; i++) {
int now = (S & (1 << i));
if(!now) { // ?x
va += x[i][j];
}
else { // ?y
va += y[i][j];
}
}
val[j] = va;
}
vector<int> tem;
bool f = 1;
for(int j = 1; j <= m; j++) {
if(val[j] > b[j]) {
f = 0;
break;
}
tem.push_back(val[j]);
}
if(f) {
if(mp[tem]) mp[tem] = min(mp[tem], __builtin_popcount(S) + 1);
else mp[tem] = __builtin_popcount(S) + 1;
}
}
n = n - nn;
for(int S = 0; S < (1 << n); S++) {
for(int j = 1; j <= m; j++) {
int va = 0;
for(int i = 0; i < n; i++) {
int now = (S & (1 << i));
if(!now) { // ?x
va += x[i + nn][j];
}
else { // ?y
va += y[i + nn][j];
}
}
val[j] = va;
}
bool f = 1;
vector<int> tem;
for(int j = 1; j <= m; j++) {
if(val[j] > b[j]) {
f = 0;
break;
}
tem.push_back(b[j] - val[j]);
}
if(f && mp[tem]) {
ans = min(ans, __builtin_popcount(S) + mp[tem] - 1);
}
}
if(ans == 100) puts("impossible");
else printf("%d\n", ans);
}
system("pause");
return 0;
}
E
给定 n 个数，还有一个数 k，你可以从 n 个数中任选两个数出来，再把 k （或 k 的一部分）分给这两个数，使得这两个数的 lcm 最大
其实是签到。
有一个性质是两个数在很小的范围内波动，它们的 lcm 是会发生很大的变化的
点击查看代码
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
int t, n, k;
int a[N];
inline ll lcm(int a, int b) {
return 1ll * a * b / __gcd(a, b);
}
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
if(a[n - 1] + k > a[n]) {
int more = k - (a[n] - a[n - 1]);
ll ans = 0;
for(int i = more / 2 - 5; i <= more / 2 + 5; i++) {
int j = more - i;
if(i <= 0 || j <= 0) continue;
ans = max(ans, lcm(a[n] + i, a[n] + j));
}
printf("%lld\n", ans);
}
else {
ll ans = 0;
for(int i = 0; i <= k; i++) {
ans = max(ans, lcm(a[n - 1] + i, a[n] + k - i));
}
printf("%lld\n", ans);
}
system("pause");
return 0;
}
总结
A. 网络流（最大流）板子题
板子至少需要能看出来吧
复习流相关知识点
C. LIS
其实也很简单，多记录一下位置就行。
看来不仅学习不扎实，在赛场上还无法冷静下来思考
一定一定要冷静，就算什么都不会，现在开始思考也是完全有可能做出来的
D. 折半搜索
去年 就不会
懂了吧
E. 签到
乱搞
怎么一点 geek 的想法都没有啊...
学会乱搞，要灵活！
F. 签到
竟然没看出来是签到，求逆序数即可
H. 图论
I. 签到
J. 维护矩阵
待补
标签：24,tem,int,ll,ans,long,vp,2022.9,define From： https://www.cnblogs.com/re0acm/p/16749418.html