场均一题放弃
A. 我
我切题了
发现图上有环可以不停的转，让空位到我们需要的地方去，而环的具体形态并不重要，我们只需要知道环的大小(\(size\))和环内元素个数(\(cnt\))即可
所以使用\(tarjan\)缩点，然后转化为一个\(DAG\)上的问题
发现环的大小等于元素个数时，我们必须先移走一个元素，然后可以加入新的元素，但原来的那个元素不能留下
在\(DAG\)转移中，我们不清楚在有多条可选择的路径中应该选择哪一条
考虑使用网络流，拆点
入点连汇点边权为\(size\)
入点连出点\(inf\)，出点连\(DAG\)上后继点的入点
当\(size == cnt\)时源点向入点连\(cnt - 1\)，向出点连\(1\)，其他情况直接连入点
这样存在最后一个小问题，当\(size == cnt == 1\)时，如果该点没有出度，那么这个孤点没有移动的理由，不应该扔掉
所以在建图前特判即可
code
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5005;
const int mx = 62;
const int inf = 2147383647;
char c[maxn];
int m, flag[maxn];
int id(char x){
if(x >= '0' && x <= '9') return x - '0' + 1;
if(x >= 'a' && x <= 'z') return x - 'a' + 10 + 1;
return x - 'A' + 10 + 26 + 1;
}
vector<int> g[maxn];
int size[maxn], cnt[maxn], sd[maxn], dt;
struct wll
{
int head[maxn], tot = 1;
struct edge{
int net, to, val;
} e[maxn << 1 | 1];
void add(int u, int v, int w){
e[++tot].net = head[u];
e[tot].val = w;
head[u] = tot;
e[tot].to = v;
}
void link(int u, int v, int w){
add(u, v, w);
add(v, u, 0);
}
int s, t;
int now[maxn], dep[maxn];
bool bfs(){
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[s] = 1;
now[s] = head[s];
q.push(s);
while (!q.empty()){
int x = q.front();
q.pop();
if(x == t) return true;
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(!dep[v] && e[i].val > 0){
now[v] = head[v];
dep[v] = dep[x] + 1;
q.push(v);
}
}
}
return false;
}
int dfs(int x, int from){
if(x == t || from <= 0)return from;
int res = from, i;
for(i = now[x]; i; i = e[i].net){
int v = e[i].to;
if(e[i].val > 0 && dep[v] == dep[x] + 1){
int k = dfs(v, min(res, e[i].val));
if(k <= 0) dep[v] = 0;
res -= k;
e[i].val -= k;
e[i ^ 1].val += k;
if(res <= 0) break;
}
}
now[x] = i;
return from - res;
}
int work(){
int ans = 0;
while (bfs()) ans += dfs(s, inf);
return ans;
}
int cd[maxn];
int init(){
for(int i = 1; i <= dt + dt + dt; ++i)head[i] = 0;
int ans = 0;
tot = 1;
for(int i = 1; i <= dt; ++i)cd[i] = 0;
s = dt + dt + 1, t = s + 1;
for(int i = 1; i <= mx; ++i)for(int v : g[i])if(sd[i] != sd[v])link(sd[i] + dt, sd[v], inf), ++cd[sd[i]];
for(int i = 1; i <= dt; ++i)if(cd[i] == 0 && cnt[i] == 1)ans += cnt[i], cnt[i] = 0, --size[i];
for(int i = 1; i <= dt; ++i)link(i, t, size[i]);
for(int i = 1; i <= dt; ++i)link(i, i + dt, inf);
for(int i = 1; i <= dt; ++i){
if(size[i] > cnt[i])link(s, i, cnt[i]);
else link(s, i, cnt[i] - 1), link(s, i + dt, 1);
}
return work() + ans;
}
}w;
int dfn[maxn], low[maxn], tim, sta[maxn], top;
bool vis[maxn];
void tarjan(int x){
low[x] = dfn[x] = ++tim;
sta[++top] = x; vis[x] = 1;
for(int v : g[x])
if(!dfn[v]) tarjan(v), low[x] = min(low[x], low[v]);
else if(vis[v]) low[x] = min(low[x], low[v]);
if(dfn[x] == low[x]){
int y; ++dt;
do{
y = sta[top--];
cnt[dt] += flag[y];
++size[dt];
sd[y] = dt;
vis[y] = 0;
} while (y != x);
}
}
queue<int> q;
void work(){
for(int i = 1; i <= mx; ++i) dfn[i] = 0;
for(int i = 1; i <= mx; ++i) low[i] = 0;
for(int i = 1; i <= mx; ++i) size[i] = 0;
for(int i = 1; i <= mx; ++i) cnt[i] = 0;
for(int i = 1; i <= mx; ++i) sd[i] = 0;
tim = 0, top = 0, dt = 0;
for(int i = 1; i <= mx; ++i) if(!dfn[i]) tarjan(i);
printf("%d\n",w.init());
}
int main()
{
freopen("graph.in", "r", stdin);
freopen("graph.out","w",stdout);
int t; scanf("%d", &t);
for(int i = 1; i <= t; ++i){
for(int i = 0; i <= mx; ++i) flag[i] = 0;
for(int i = 0; i <= mx; ++i) g[i].clear();
scanf("%s", c + 1);
int len = strlen(c + 1);
for(int i = 1; i <= len; ++i)flag[id(c[i])] = 1;
scanf("%d", &m);
for(int i = 1; i <= m; ++i)scanf("%s", c), g[id(c[0])].push_back(id(c[1]));
work();
}
return 0;
}
B. 想不出
可以想象翻转了坐标轴，向左或者下射线，存在一条折线，其左上都向下，右下都向左
然后，不会了，看上届学长的题解，作法是看左侧交点多还是下方交点多来定向，不是很理解很是不理解
code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
inline int max(int x, int y){return x > y ? x : y;}
inline int min(int x, int y){return x < y ? x : y;}
inline void swap(int &x, int &y){x ^= y, y ^= x, x ^= y;}
const int maxn = 2005;
const int inf = 2147383647;
int n;
struct node{
int x,y;
double k1, b1, k2, b2;
bool operator < (const node &b)const{return x == b.x ? y < b.y : x < b.x;}
}d[maxn];
int dir[maxn], vis[maxn];
bool check(int x, int y){
double a = (d[y].b1 - d[x].b2) / (d[x].k2 - d[y].k1);
return d[x].x <= a && a <= d[y].x;
}
int main(){
freopen("surface.in","r",stdin);
freopen("surface.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; ++i)scanf("%d%d",&d[i].x, &d[i].y);
sort(d + 1, d + n + 1);
for(int i = 1; i <= n; ++i){
d[i].k1 = (double) sqrt(3);
d[i].k2 = -d[i].k1;
d[i].b1 = d[i].y - d[i].k1 * d[i].x;
d[i].b2 = d[i].y - d[i].k2 * d[i].x;
}
for(int i = 1; i <= n; ++i){
int c1 = 0, c2 = 0;
for(int j = 1; j < i; ++j)if(check(j, i))++c1;
for(int j = n; j > i; --j)if(check(i, j))++c2;
dir[i] = c1 < c2 ? 1 : 0;
}
int ans = 0;
for(int i = 1; i <= n; ++i)
if(dir[i]){
int now = -1;
for(int j = i + 1; j <= n; ++j)if(!dir[j])
if(check(i, j)){if(!vis[j])vis[j] = 1; else ++now;}
ans += max(now, 0);
}
printf("%d\n",ans);
return 0;
}
C. 题目名称
不要被数据范围吓到，背包有\(45pts\)
正解不会
45
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
inline int max(int x, int y){return x > y ? x : y;}
inline int min(int x, int y){return x < y ? x : y;}
inline void swap(int &x, int &y){x ^= y, y ^= x, x ^= y;}
inline ll read(){
ll x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
const int maxn = 1000005;
const int inf = 2147383647;
const int mod = 998244353;
ll n, s;
ll f[5][maxn];
int vis[maxn];
void work(int l, int r){
for(int i = l; i <= r; ++i){
if(vis[i]){i = vis[i];continue;} vis[i] = r;
for(int k = 3; k >= 0; --k)
for(int j = 0; j <= s - i; ++j)
f[k + 1][j + i] = (f[k + 1][j + i] + f[k][j]) % mod;
}
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
n = read(), s = read();
f[0][0] = 1;
for(int i = 1; i <= n; ++i){
int l = read(), r = read();
work(l, r);
}
printf("%lld\n",f[4][s]);
return 0;
}