T1[状态压缩DP]给出\(n,m,p,q,r\),求长度是n，值域在\([1,m]\)之间的序列个数，满足\(\exists 1\leq x<y<z<k\leq n,\)\(sum(x,y-1)=p,sum(y,z-1)=q,sum(z,k)=r\).(n<=50,max(p,q,r)<=6)
考场
想到数位DP，依次确定每一位填什么，维护到目前位数的连续段,\(bit,now,lef\),表示填到a的第bit位，连续的pqr已经填到了now，now位还差lef个数填满，每次枚举填什么，\([1,lef]\)填可以有进位1的贡献，\([lef+1,v[1]]\)有从1置位的贡献
\(max(v[1],m)-m\)是置0的贡献，只统计合法位置第一次出现，剩下的就是一个次方。
结果它总是少算啊，怎么搞都少，没辙了，交了暴力10pts
正解
问题是什么？是你在x位置匹配不合法不一定会回退到1位置，可能是回退到某个位继续贡献（就是你强制的到目前不合法不管用了，可能填着填着合法了但是你不知道，于是就算少了），这样就不能只保留最后一位信息，需要保留更多。多到多少呢？发现pq,r很小，那么合法的一段缀应该是长度<=18的，而且\(s1+s2+s3=p+q+r,s1=p,s2=q,s3=r\),一看就不多，打表发现最多有10万多个，于是就考虑直接计算出这些状态然后转移
\(t[S][j]:表示目前状态是S，如果在后面再接一个数j，序列会变成的序列编号。\)
dfs进行枚举每次填什么，在这个基础上枚举再填一位会发生什么变化，如果\(islegal\),状态设置-1,
否则更新map新状态加入。注意维护的是一段后缀，所以每个状态只保留\(<sum\)的部分，=sum的部分作为不合法状态已经设置-1了。
DP就是模拟填数过程
\(O(n*(min(m,6))*state_{cnt})\)
%%%APjifengc
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define ull unsigned long long
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
const int N = 2e5 + 100;
const int mod = 998244353;
int n, m, p, q, r;
int f[2][N], t[N][8];
int cnt, pw[N];
struct State {
deque<int> q;
int sum;
void push(int x) {
q.push_front(x);
sum += x;
}
void pop() {
sum -= q.back();
q.pop_back();
}
};
struct Hash {
int hs1, hs2;
void clear() { hs1 = hs2 = 0; }
void operator+=(int A) {
hs1 = (1ll * hs1 * 13331 + A) % 993244853;
hs2 = (1ll * hs2 * 131 + A) % 1000000009;
}
bool operator==(const Hash& A) const { return hs1 == A.hs1 && hs2 == A.hs2; }
size_t operator()(const Hash& A) const { return A.hs1 ^ A.hs2; }
};
unordered_map<Hash, int, Hash> mp;
inline Hash getHash(State& s) {
Hash hsh;
hsh.clear();
for (rint ele : s.q) hsh += ele;
return hsh;
}
State tt;
inline void dfs(int s) {
if (s >= p + q + r)
return;
// printf("s；%d\n",s);
Hash now = getHash(tt);
if (!mp.count(now))
mp[now] = ++cnt;
int nid = mp[now];
for (rint i = 1; i <= min(6, m); ++i) {
State ls = tt;
ls.push(i);
while (ls.sum > p + q + r) ls.pop();
if (ls.sum == p + q + r) {
// printf("%d equal\n",i);
int ar = 0, br = 0, cr = 0;
for (rint j : ls.q) {
if (ar != p) {
ar += j;
if (ar > p)
break;
} else if (br != q) {
br += j;
if (br > q)
break;
} else if (cr != r) {
cr += j;
if (cr > r)
break;
}
}
if (ar == p && br == q && cr == r) {
// printf("%d %d no\n",nid,i);
t[nid][i] = -1;
continue;
}
}
while (ls.sum >= p + q + r) ls.pop();
Hash uu = getHash(ls);
if (!mp.count(uu))
mp[uu] = ++cnt;
int newid = mp[uu];
t[nid][i] = newid;
}
for (rint i = 1; i <= min(6, m); ++i) {
State orz;
orz = tt;
tt.push(i);
dfs(s + i);
tt = orz;
}
}
int main() {
// freopen("1.in","r",stdin);
// freopen("2.out","w",stdout);
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
n = re(), m = re(), p = re(), q = re(), r = re();
mp[(Hash){ 0, 0 }] = 0;
dfs(0);
pw[0] = 1;
for (rint i = 1; i <= n; ++i) pw[i] = 1ll * pw[i - 1] * m % mod;
int o = 0;
f[o][0] = 1;
int ans = 0;
// chu("%d\n",cnt);int rr=0;
// for(rint i=1;i<=cnt;++i)
// for(rint j=1;j<=4;++j)if(t[i][j]==-1)++rr;
// chu("r:%d\n",rr);
for (rint i = 1; i <= n; ++i, o ^= 1) {
memset(f[o ^ 1], 0, sizeof(f[o ^ 1]));
for (rint j = 0; j <= cnt; ++j) {
if (f[o][j]) {
int v = f[o][j];
for (rint k = 1; k <= min(m, 6); ++k) {
int rel = t[j][k];
if (rel == -1) {
ans = (ans + 1ll * v * pw[n - i] % mod) % mod;
continue;
}
f[o ^ 1][rel] = (f[o ^ 1][rel] + v) % mod;
}
if (m > 6) {
f[o ^ 1][0] = (f[o ^ 1][0] + 1ll * v * (m - 6) % mod) % mod;
}
}
}
}
chu("%d", ans);
return 0;
}
/*
10 5 3 5 4
*/
T3[图论/贪心]n个点的无向有权图，可以任意次交换边权，求\((u,v)(v,w)\)最短路之和。(n<=2e5)
考场
这不就是分类讨论一下嘛，边权取前k小sort一下呗。
最直接想到\(u->v\)记录一个1为边权的最短路，然后v再计算一遍到w，发现路径可以重复，于是跑DIJ记录最短路劲上的点，枚举重复的点O(1)计算贡献。
正解
差一步，差什么呢？
因为你不一定是要跑u,v最短路径上的点，任意点都可以成为决策！
还有就是下标炸了。
点击查看代码
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define ull unsigned long long
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
const int N = 2e5 + 100;
int n, m, u, v, w;
int c[N], tot = 1;
ll sum[N];
int dis[3][N], head[N];
int ind[N], Ind;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
bool vis[N];
struct node {
int to, nxt;
} e[N << 1];
inline void add_e(int x, int y) {
e[++tot] = (node){ y, head[x] };
head[x] = tot;
}
inline void dij(int st, int opt) {
memset(dis[opt], 0x3f, sizeof(dis[opt]));
dis[opt][st] = 0;
fill(vis + 1, vis + 1 + n, 0);
q.push(make_pair(0, st));
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (rint i = head[x]; i; i = e[i].nxt) {
int to = e[i].to;
if (dis[opt][to] > dis[opt][x] + 1) {
dis[opt][to] = dis[opt][x] + 1;
q.push(make_pair(dis[opt][to], to));
}
}
}
}
int main() {
// freopen("c3.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
n = re(), m = re(), u = re(), v = re(), w = re();
for (rint i = 1; i <= m; ++i) {
int ai = re(), bi = re(), ci = re();
add_e(ai, bi);
add_e(bi, ai);
c[i] = ci;
}
sort(c + 1, c + 1 + m);
for (rint i = 1; i <= m; ++i) sum[i] = sum[i - 1] + c[i];
dij(u, 0);
dij(v, 1);
dij(w, 2);
for (rint i = 1; i <= n; ++i) ind[++Ind] = i;
// for(rint i=1;i<=n;++i)chu("u:disto:%d is :%d\n",i,dis[1][i]);
// for(rint i=1;i<=Ind;++i)chu("ind[%d]:%d\n",i,ind[i]);
ll ans = 1e18;
for (rint i = 1; i <= Ind; ++i) //枚举从u->v，从v去到w路径上的重合部分
{
ll nowans = 0;
int cut = dis[1][ind[i]];
int d1 = dis[0][ind[i]], d2 = dis[2][ind[i]];
int d = d1 + d2;
if (d1 + d2 + cut > m)
continue;
nowans = sum[cut + d] + sum[cut], ans = min(ans, nowans);
}
chu("%lld", ans);
return 0;
}
/*
边权赋值1，求最短路
dis[u][]
dis[v][]
dis[w][]
把u,v上的最短路径拿出来,枚举断点
*/
T4[图论/欧拉路]给你n条线段(x1,y1)(x2,y2),保证水平或者竖直，要你求最少多少次落笔，覆盖这些线段K次。(K,n<=2e3,x,y<=1e6)
考场
手摸一下发现就是欧拉路问题，覆盖线段K次看成有K条边，要求走完这些边的最少落笔次数，考虑奇数点成对出现，每次落笔只能最多消灭一对奇数点，而且矛盾点只在奇数点，（考虑多一条边消灭奇数点，那么偶数点就是欧拉回路），所以对于一个连通图，下笔次数是\(max(1,cnt/2)\),cnt是奇数点个数。如果不连通，就是多一个联通快多一次落笔，+1就行。注意第一次落笔不算要-1.
对，这些都是考场的想法，然后开始打，发现把线段转化点非常恶心，开始枚举线段横竖\(n^2\),枚举寻找左边第一个小于，上边第一个小于，端点又是4个大循环畅快讨论，200多行过去了，1个半小时过去了，发现连图都没建呢，复杂度也假了，果断放弃。
正解
首先结论继承上面的，然后大谈建点:
先把点拿出来，具体的，端点加入，然后交点加入，去重？这种事情不要一堆ifelse，直接map上
然后考虑连边，发现无论是枚举线段交点找点，还是枚举点找4个方向都麻烦得不行，考虑直接枚举线段对点的贡献，直接横着竖着扫一遍每条线段联通的一条线上的点,然后再考虑横竖之间的...等等！？没了？这就是全部？神奇！
\(O(n^2logn)\)
点击查看代码
// ubsan: undefined
// accoders
//鹤都鹤T了我也是够了，找不同功底日益深厚...
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
#define ull unsigned long long
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
const int N = 4100;
int n, m, cnt;
map<pair<int, int>, bool> mp2; //对点对进行映射去重
struct edge {
int to, nxt;
} e[N * N * 4];
int head[N * N], tot;
vector<pair<int, int> > ph[N], ps[N],
tmp; //存横坐标或者纵坐标意义下的线段对，是为了建立点,也方便到时候对边找贡献
//还要搞一个tmp，因为重复的线段需要处理
//点也要放进去，分横和纵的
int mpx[N << 1], mpy[N << 1], mmx, mmy;
vector<int> dh[N], ds[N];
struct linshi {
int a1, b1, a2, b2;
} lsp[N];
int deg[N * N];
bool vis[N * N];
vector<int> vec;
inline void add(int x, int y) {
e[++tot] = (edge){ y, head[x] };
head[x] = tot;
}
inline void add_e(int x, int y) {
if (mp2.count(make_pair(x, y)) == 0) {
// chu("%d--%d\n",x,y);
add(x, y);
add(y, x);
mp2[make_pair(x, y)] = 1;
}
}
int mp[4000 + 10][4000 + 10];
inline void insert(int x, int y) {
// chu("insert:%d %d\n",x,y);
if (mp[x][y] == 0)
mp[x][y] = ++cnt, dh[x].push_back(y), ds[y].push_back(x); // chu("succode\n");//加入点
// else chu("NO\n");
}
inline bool Jiao(int x, pair<int, int> xl, int y, pair<int, int> yl) {
if (x <= yl.second && x >= yl.first && y <= xl.second && y >= xl.first)
return 1;
return 0;
}
inline void dfs(int x) {
vec.push_back(x);
vis[x] = 1;
for (rint i = head[x]; i; i = e[i].nxt) {
++deg[x]; //就是度数
int to = e[i].to;
if (vis[to])
continue;
dfs(to);
}
}
int use[N], use2[N];
int main() {
freopen("d.in", "r", stdin);
freopen("d.out", "w", stdout);
// freopen("d.in","r",stdin);
// freopen("d.out","w",stdout);
m = re(), n = re();
for (rint i = 1; i <= m; ++i) {
lsp[i].a1 = re(), lsp[i].b1 = re(), lsp[i].a2 = re(), lsp[i].b2 = re();
mpx[++mmx] = lsp[i].a1;
mpx[++mmx] = lsp[i].a2;
mpy[++mmy] = lsp[i].b1;
mpy[++mmy] = lsp[i].b2;
}
sort(mpx + 1, mpx + 1 + mmx);
sort(mpy + 1, mpy + 1 + mmy);
mmx = unique(mpx + 1, mpx + 1 + mmx) - mpx - 1;
mmy = unique(mpy + 1, mpy + 1 + mmy) - mpy - 1;
for (rint i = 1; i <= m; ++i) {
lsp[i].a1 = lower_bound(mpx + 1, mpx + 1 + mmx, lsp[i].a1) - mpx;
lsp[i].b1 = lower_bound(mpy + 1, mpy + 1 + mmy, lsp[i].b1) - mpy;
lsp[i].a2 = lower_bound(mpx + 1, mpx + 1 + mmx, lsp[i].a2) - mpx;
lsp[i].b2 = lower_bound(mpy + 1, mpy + 1 + mmy, lsp[i].b2) - mpy;
if (lsp[i].a1 > lsp[i].a2)
swap(lsp[i].a1, lsp[i].a2);
if (lsp[i].b1 > lsp[i].b2)
swap(lsp[i].b1, lsp[i].b2);
// chu("%d %d %d %d\n",lsp[i].a1,lsp[i].b1,lsp[i].a2,lsp[i].b2);
if (lsp[i].a1 == lsp[i].a2) {
ph[lsp[i].a1].push_back(make_pair(lsp[i].b1, lsp[i].b2));
} else {
ps[lsp[i].b1].push_back(make_pair(lsp[i].a1, lsp[i].a2));
}
}
// return 0;
// chu("dfsrewr\n");
for (rint i = 1; i <= mmx; ++i) {
sort(ph[i].begin(), ph[i].end());
int sz = ph[i].size();
tmp.clear();
int rem = -1;
for (rint j = 0; j < sz; ++j) {
if (rem == -1 || ph[i][j].first > ph[i][rem].second) {
if (rem != -1)
tmp.push_back(ph[i][rem]);
rem = j;
} else {
ph[i][rem].second = max(ph[i][rem].second, ph[i][j].second);
}
}
if (rem != -1)
tmp.push_back(ph[i][rem]);
ph[i] = tmp;
}
// chu("dfs\n");
for (rint i = 1; i <= mmy; ++i) {
sort(ps[i].begin(), ps[i].end());
int sz = ps[i].size();
tmp.clear();
int rem = -1;
for (rint j = 0; j < sz; ++j) {
if (rem == -1 || ps[i][j].first > ps[i][rem].second) {
if (rem != -1)
tmp.push_back(ps[i][rem]);
rem = j;
} else {
ps[i][rem].second = max(ps[i][rem].second, ps[i][j].second);
}
}
if (rem != -1)
tmp.push_back(ps[i][rem]);
ps[i] = tmp;
}
// for(rint i=1;i<=mmy;++i)
// {
// for(auto j:ps[i])chu("for:%d is %d %d\n",i,j.first,j.second);
// }
// chu("dfsdf\n");
for (rint i = 1; i <= mmx; ++i)
if (ph[i].size())
use[++use[0]] = i;
for (rint i = 1; i <= mmy; ++i)
if (ps[i].size())
use2[++use2[0]] = i;
for (rint I = 1; I <= use[0]; ++I) {
int i = use[I];
// chu("i:%d(%d)\n",i,ph[i].size());
for (pair<int, int> j : ph[i]) //遍历线段
{
// chu("in?\n");
insert(i, j.first);
insert(i, j.second);
for (rint II = 1; II <= use2[0]; ++II) {
int ii = use2[II];
// chu("ii:%d(%d)\n",ii,ps[ii].size());
for (pair<int, int> jj : ps[ii]) //找交点，啊，要T的感觉
{
insert(jj.first, ii);
insert(jj.second, ii);
// chu("wher slow:%d\n",jj.first);
if (Jiao(i, j, ii, jj)) //有交点
{
insert(i, ii);
}
}
}
}
}
// chu("dfdsfds\n");
for (rint I = 1, i = use[I]; I <= use[0]; ++I, i = use[I]) {
sort(dh[i].begin(), dh[i].end());
// for(rint j:dh[i])chu("dot:(%d %d)(id:%d)\n",i,j,mp[(node){i,j}]);
}
// chu("dfsdfdssdf\n");
for (rint I = 1, i = use2[I]; I <= use2[0]; ++I, i = use2[I]) {
sort(ds[i].begin(), ds[i].end());
// chu("siz[%d]:%ld\n",i,ds[i].size());
// for(rint j:ds[i])chu("sdot:(%d %d)\n",j,i);
}
// return 0;
//点有了，编号也有了，然后就是用线段连
//遍历线段
// chu("he is out\n");
for (rint I = 1, i = use[I]; I <= use[0]; ++I, i = use[I]) {
//是横着的
for (pair<int, int> j : ph[i]) //找到它的端点位置
{
int p1 = lower_bound(dh[i].begin(), dh[i].end(), j.first) - dh[i].begin();
int p2 = lower_bound(dh[i].begin(), dh[i].end(), j.second) - dh[i].begin();
// p1--p2连接
for (rint k = p1; k < p2; ++k) {
add_e(mp[i][dh[i][k]], mp[i][dh[i][k + 1]]);
}
}
}
// chu("dfdsfsdfdsfdsfdsf\n");
for (rint I = 1, i = use2[I]; I <= use2[0]; ++I, i = use2[I]) {
//是横着的
for (pair<int, int> j : ps[i]) //找到它的端点位置
{
int p1 = lower_bound(ds[i].begin(), ds[i].end(), j.first) - ds[i].begin();
int p2 = lower_bound(ds[i].begin(), ds[i].end(), j.second) - ds[i].begin();
// p1--p2连接
for (rint k = p1; k < p2; ++k) {
add_e(mp[ds[i][k]][i], mp[ds[i][k + 1]][i]);
}
}
}
//然后边就连完了,跑图？
int ans = -1;
for (rint i = 1; i <= cnt; ++i)
if (!vis[i]) {
++ans; //一个独立图+1
dfs(i);
if (n & 1) //是奇数
{
int sad = 0;
for (rint j : vec)
if (deg[j] & 1)
++sad; // chu("%d is in(%d)\n",j,deg[j]);
ans += max(0, sad / 2 - 1);
// chu("start is:%d the sad:%d\n",i,sad);
// chu("now ans:%d\n",ans);
vec.clear();
}
//是偶数就不管了
}
chu("%d", ans);
return 0;
}
/*
4 1
1 1 1 0
1 1 0 1
1 1 1 2
1 0 1 2
枚举每个线段，枚举方向不一样的线段，统计交点。
考虑对于(x,y):
[1]上面有边：存在上面的线段在子线段中，包含了y
[2]右边有边：存在右边的线段在子线段中，包含了x
所以init_deg=0--4
然后*m，判断奇数偶数直接讨论了
但是如果m是偶数，直接就是偶数，还要算个寄
开始猜结论
通过一些途径统计出点，然后连边
统计度数是奇数的点=cnt
if(cnt<=2)ans=1;
else ans=cnt/2
记得-1！
不同联通块，+=code-1
*/