T1[数论/贪心构造]给出n-1对限制形如(i,j,a,b),要求\(xi/xj=a/b\),xi和xj都是正整数。求长度是n的序列x，满足条件（保证给定条件和任意一个数可以唯一确定这个序列）的\(min(\sum xi)\mod998244353\).(n<=2e5,a,b<=n)
正解
简单模拟可以发现如果选择任意一个点当做根，设为1，可以唯一推断出其他数用分数表示，那么最小的x就是所有数*上最简分式的分母的lcm。考虑求lcm，如果直接暴力计算会T，考虑另一种lcm的求法：\(p^{max_{appearcnt}}\),用一个buc数组，在分母的时候记录，分子消除（因为约分可以消掉一些），注意每个时刻都要记录min，维护的是从root到路径上的桶。
const int mod = 998244353, N = 2e5 + 100;
inline ll qpow(ll ak, ll bk) {
ll ck = 1;
while (bk) {
if (bk & 1)
ck = 1ll * ck * ak % mod;
ak = 1ll * ak * ak % mod;
bk >>= 1;
}
return ck;
}
int head[N], tot, n;
bool prime[N];
int zhi[N], cnt, mi[N], lcm, buc[N], rec[N], val[N], inv[N];
struct node {
int to, nxt, a, b;
} e[N << 1];
inline void Shai() {
for (rint i = 2; i <= (int)2e5; ++i) {
if (!prime[i])
zhi[++cnt] = i, mi[i] = i;
for (rint j = 1; j <= cnt; ++j) {
if ((int)2e5 / zhi[j] < i)
break;
int now = zhi[j] * i;
mi[now] = zhi[j];
prime[now] = 1;
if (i % zhi[j] == 0)
break;
}
}
inv[0] = inv[1] = 1;
for (rint i = 2; i <= int(2e5); ++i) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}
inline void add_e(int x, int y, int a, int b) {
e[++tot] = (node){ y, head[x], a, b };
head[x] = tot;
}
inline void chmin(int& x, int y) { x = (x > y) ? y : x; }
vector<int> stk;
inline void insert(int x, int vl) {
while (x > 1) {
int o = mi[x];
int ct = 0;
while (x > 1 && x % o == 0) x /= o, ++ct;
buc[o] += vl * ct;
// chmin(rec[o],buc[o]);
// if(vl<0)stk[++top]=o;//涉及到的质因子
if (vl < 0)
stk.push_back(o);
}
}
inline void dfs(int x, int ff) {
// chu("now 3:%d(buc:%d)\n",rec[3],buc[3]);
for (rint i = head[x]; i; i = e[i].nxt) {
int to = e[i].to;
if (to == ff)
continue;
insert(e[i].a, -1);
insert(e[i].b, 1);
for (rint j : stk) chmin(rec[j], buc[j]);
stk.clear();
dfs(to, x);
insert(e[i].a, 1);
insert(e[i].b, -1);
}
}
inline void Dfs(int x, int ff) {
// val[x]=1ll*val[x]*lcm%mod;
// chu("udpoate val[%d]:%d()\n",x,val[x]);
for (rint i = head[x]; i; i = e[i].nxt) {
int to = e[i].to;
if (to == ff)
continue;
// chu("%d %d %d\n",val[to],inv[e[i].a],e[i].b);
val[to] = 1ll * val[x] * inv[e[i].a] % mod * e[i].b % mod;
// chu("now val to")
Dfs(to, x);
}
}
inline void deal() {
n = re();
for (rint i = 1; i <= n; ++i) buc[i] = rec[i] = 0, val[i] = 1;
for (rint i = 1; i < n; ++i) {
int I = re(), J = re(), a = re(), b = re();
add_e(I, J, a, b);
add_e(J, I, b, a);
}
dfs(1, 0); //任意起点
lcm = 1;
for (rint i = 2; i <= n; ++i)
if (rec[i] < 0)
lcm = 1ll * lcm * qpow(i, -rec[i]) % mod; // chu("rec[%d]:%d\n",i,rec[i]);
// chu("lcm:%d\n",lcm);
val[1] = lcm;
Dfs(1, 0);
int ret = 0;
// chu("val1:%d\n",val[1]);
for (rint i = 1; i <= n; ++i) ret = (1ll * ret + 1ll * val[i]) % mod; // chu("val[%d]；%d\n",i,val[i]);
chu("%d\n", ret);
}
int main() {
freopen("arrange.in", "r", stdin);
freopen("arrange.out", "w", stdout);
// freopen("1.in","r",stdin);
// freope("1.out","w",stdout);
int T = re();
Shai();
while (T--) {
tot = 0;
for (rint i = 1; i <= n; ++i) head[i] = 0;
deal();
}
return 0;
}
T2[数据结构/思维]给出长度是n的01序列，求\(\sum_{l\epsilon[1,n],r\epsilon[l,n]}Max(l,r) ,Max(l,r)是子序列[l,r]最长连续1的长度\)。
正解
【1】一看统计区间想移动断点统计贡献，容易想到固定右端点，线段树维护连续段，那么值从左到右不递增，每次修改，从1-非当前连续段贡献是len,连续段是len-dis(p,i),考虑分开维护需要线段树同时支持覆盖和加标记，不好搞，于是把线段树二分换成树外二分，好处就是可以把now的连续段也同时分进去，直接价值+1就可以了，定义\(f[i]\)是1--i的最长连续1长度（必须包含当前位置），容易发现贡献就是\(min(f[i],i-p+1)\),\(O(n*logn^2)\)
// ubsan: undefined
// accoders
//%%%Jersan大佬
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rint register int
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
h = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * h;
}
#define int ll
const int N = 5e5 + 100, inf = 1e9;
int n, sum[N]; // sum维护左边最长连续1长度
char s[N];
struct SegmentTree {
ll sum[N << 2]; //一个就够了？
int tag[N << 2];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) >> 1)
inline void pushup(int rt) { sum[rt] = sum[lson] + sum[rson]; }
inline void pushdown(int rt, int l, int r) {
if (!tag[rt])
return;
tag[lson] += tag[rt];
tag[rson] += tag[rt];
sum[lson] += 1ll * tag[rt] * (mid - l + 1);
sum[rson] += 1ll * tag[rt] * (r - mid);
tag[rt] = 0;
}
inline void insert(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) {
tag[rt]++;
sum[rt] += (r - l + 1);
return;
}
pushdown(rt, l, r);
if (L <= mid)
insert(lson, l, mid, L, R);
if (R > mid)
insert(rson, mid + 1, r, L, R);
pushup(rt);
}
inline int query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R)
return sum[rt];
pushdown(rt, l, r);
if (R <= mid)
return query(lson, l, mid, L, R);
if (L > mid)
return query(rson, mid + 1, r, L, R);
return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
}
#undef lson
#undef rson
#undef mid
} seg;
inline bool better(int mid, int p) {
// chu("%d--%d is :%d(query:%d)\n",seg.query(1,1,n,mid,mid),mid,p,min(sum[mid],p-mid+1));
return seg.query(1, 1, n, mid, mid) < min(sum[p], p - mid + 1);
}
signed main() {
// freopen("1.in","r",stdin);
// freopen("2.out","w",stdout);
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
n = re();
scanf("%s", s + 1);
for (rint i = 1; i <= n; ++i) {
if (s[i] == '1')
sum[i] = sum[i - 1] + 1;
}
ll summ = 0, lastans = 0;
for (rint i = 1; i <= n; ++i) {
if (s[i] == '0') {
summ += lastans;
} else {
sum[i] = sum[i - 1] + 1;
int l = 1, r = i;
int goal = i;
while (l <= r) {
int mid = (l + r) >> 1;
if (better(mid, i))
goal = mid, r = mid - 1;
else
l = mid + 1;
}
// chu("shoud change:%d--%d\n",goal,i);
if (goal <= i)
seg.insert(1, 1, n, goal, i);
lastans = seg.query(1, 1, n, 1, i);
summ += lastans;
}
// chu("lastasn(%d):%lld\n",i,lastans);
}
chu("%lld", summ);
return 0;
}
/*
4
0110
我一定能写对线段树二分！
*/
【2】考虑贡献来源，每次给连续段+1，假设目前连续段长度len，那么先继承上一位答案，新的贡献是\(i-pre[len-1]+1\),就是这些区间的答案是要update成len的。每次从1到0更新pre，0到1就直接看答案。
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 2;
const int mod = 998244353;
char s[maxn];
int n, pre[maxn], suf[maxn], fir, las, p0[maxn];
ll ans, sum;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
//啊我知道错哪儿了！！
//……5e5……
//等我把没用的调试删一删
n = read();
scanf("%s", s + 1);
int len = 0;
for (int i = n; i >= 1; i--) {
if (s[i] == '1')
len++;
else
len = 0;
suf[i] = len;
}
for (int i = 1; i <= n; i++) {
if ((i == 1 && s[i] == '1') || (s[i] == '1' && s[i - 1] == '0')) {
if (fir) {
for (int j = fir; j < i; j++) {
pre[suf[j]] = j;
if (s[j] == '0')
break;
}
}
fir = i;
}
if (s[i] == '1')
sum += i - pre[i - fir + 1], las = i;
ans += sum;
}
printf("%lld\n", ans);
return 0;
}
T3[构造/规律]给出n对多米诺(x,y),求把这n对多米诺拼成m*k的矩阵（mk自己定）的方案，要求输出2种，而且2种方案任意位置的牌摆放方式不同。(n<=3e5)
正解
观察构造，可以发现都是形如
[1]
AB
BC
[2]
ABC
BDB
[3]
ABB
CCD
，这样去匹配为什么呢？可以把点看成图，那么【1】可以消除长度是2的链，
【1】可以消除菊花，【3】可以消除3的链。多试一试，发现除了只有a-b的单链情况，其他都是有合法解的。
怎么构造？
可以贪心用堆去配，先2元，再3元
为了能完全匹配钦定大小顺序，保证非匹配出现在后面。
简化分类讨论，swap解决。记录编号，不暴力的拆出每一个二元组。
#include<bits/stdc++.h>
using namespace std;
#define chu printf
#define rint register int
#define ll long long
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
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=3e5+100,M=2e6+10;
int bl[N],jl[M][3],tot;
int ans[N][2];
char ta[N][2],tb[N][2];
struct node
{
int x,y,id;
inline bool operator<(const node & U)const
{
return (x==U.x)?(y>U.y):(x>U.x);
}
}a[N];
vector<int>g[N<<1];
int n;
priority_queue<node>q;
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
freopen("domino.in","r",stdin);
freopen("domino.out","w",stdout);
n=re();
for(rint i=1;i<=n;++i)
{
a[i].x=re(),a[i].y=re();
if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
}
sort(a+1,a+1+n,[&](node A,node B){return (A.x==B.x)?(A.y<B.y):(A.x<B.x);});
for(rint i=1;i<=n;++i)
{
q.push((node){a[i].x,a[i].y,i});
g[a[i].x].push_back(i);
g[a[i].y].push_back(i);
}
node A,B,ls=(node){0,0,0};
while(!q.empty())
{
A=q.top();q.pop();
if(!q.empty())B=q.top();
else B=(node){0,0,0};
if(A.x==B.x)
{
++tot;
bl[A.id]=bl[B.id]=tot;
jl[tot][0]=A.id;
jl[tot][1]=B.id;
q.pop();
ls=B;
}
else
{
if(A.x==ls.x)
{
bl[A.id]=bl[ls.id];
jl[bl[ls.id]][2]=A.id;
}
else
{
bool vius=0;
for(rint i=0;i<g[A.x].size();++i)
{
int id=g[A.x][i];
if(!bl[id])continue;
vius=1;
if(jl[bl[id]][2])
{
if(a[jl[bl[id]][0]].y==A.x)
swap(jl[bl[id]][0],jl[bl[id]][1]),swap(jl[bl[id]][1],jl[bl[id]][2]);
if(a[jl[bl[id]][1]].y==A.x)
swap(jl[bl[id]][1],jl[bl[id]][2]);
++tot;
int pre=jl[bl[id]][2];
jl[bl[id]][2]=0;
jl[tot][0]=pre;
jl[tot][1]=A.id;
bl[pre]=bl[A.id]=tot;
}
else
{
jl[bl[id]][2]=A.id;
bl[A.id]=bl[id];
}
break;
}
if(!vius)
{
if(A.x<A.y)
{
q.push((node){A.y,A.x,A.id});
swap(a[A.id].x,a[A.id].y);
}
else
{
chu("-1");return 0;
}
}
}
}
}
int l=1;
for(rint i=1;i<=tot;++i)
{
int p1=jl[i][0],p2=jl[i][1],p3=jl[i][2];
if(!p3)
{
if(a[p1].x==a[p2].x)
{
ans[l][0]=a[p1].x;
ans[l][1]=a[p1].y;
ans[l+1][0]=a[p2].y;
ans[l+1][1]=a[p2].x;
}
else
{
ans[l][0]=a[p1].x;
ans[l][1]=a[p1].y;
ans[l+1][0]=a[p2].x;
ans[l+1][1]=a[p2].y;
}
l+=2;
}
else
{
if(a[p1].x==a[p2].x&&a[p2].x==a[p3].x)
{
ans[l][0]=ans[l+1][1]=ans[l+2][0]=a[p1].x;
ans[l][1]=a[p1].y;
ans[l+1][0]=a[p2].y;
ans[l+2][1]=a[p3].y;
}
else
{
if(a[p1].x==a[p3].x)swap(p2,p3);
if(a[p2].x==a[p3].x)swap(p1,p3);
if(a[p1].y==a[p3].x)swap(p1,p2);
if(a[p1].x!=a[p2].x&&a[p2].x!=a[p3].x)
{
ans[l][0]=a[p1].x;
ans[l][1]=a[p1].y;
ans[l+1][0]=a[p2].x;
ans[l+1][1]=a[p2].y;
ans[l+2][0]=a[p3].x;
ans[l+2][1]=a[p3].y;
}
else
{
ans[l][0]=a[p1].y;
ans[l][1]=a[p1].x;
ans[l+1][0]=a[p2].x;
ans[l+1][1]=a[p2].y;
ans[l+2][0]=a[p3].x;
ans[l+2][1]=a[p3].y;
}
}
l+=3;
}
}
l=1;
// chu("tot:%d\n",tot);
for(rint i=1;i<=tot;++i)
{
int p1=jl[i][0],p2=jl[i][1],p3=jl[i][2];
// chu("%d %d %d\n",p1,p2,p3);
if(!p3)
{
//chu("in\n");
ta[l][0]='U';
ta[l][1]='D';
ta[l+1][0]='U';
ta[l+1][1]='D';
tb[l][0]='L';
tb[l+1][0]='R';
tb[l][1]='L';
tb[l+1][1]='R';
l+=2;
}
else
{
ta[l][0]='U';
ta[l][1]='D';
ta[l+1][0]='L';
ta[l+2][0]='R';
ta[l+1][1]='L';
ta[l+2][1]='R';
tb[l][0]='L';
tb[l+1][0]='R';
tb[l][1]='L';
tb[l+1][1]='R';
tb[l+2][0]='U';
tb[l+2][1]='D';
l+=3;
}
}
chu("2 %d\n",n);
for(rint i=1;i<=n;++i)
{
chu("%d ",ans[i][0]);
}
chu("\n");
for(rint i=1;i<=n;++i)
{
chu("%d ",ans[i][1]);
}
chu("\n");
for(rint i=1;i<=n;++i)
{
chu("%c",ta[i][0]);
}
chu("\n");
for(rint i=1;i<=n;++i)
{
chu("%c",ta[i][1]);
}
chu("\n");
for(rint i=1;i<=n;++i)
{
chu("%c",tb[i][0]);
}
chu("\n");
for(rint i=1;i<=n;++i)
{
chu("%c",tb[i][1]);
}
return 0;
}
/*
*/
T4[计数DP/转化]给出2个长度n的01序列，你可以进行操作，每次【1】把相邻00变11【2】相邻11变00，求所有最少操作次数总和（p和q序列有？代表值不确定）\(\mod 1e9+7\)。(n<=1000)
正解
神奇的转化，把奇数位^上1，那么问题变成了交换相邻2个01，求最终使得2个虚列合法的操作数。
首先一个套路就是位置pos被跨越的次数就是\(\sum_{i<=pos} pi-qi\)
所有位置的跨越次数和就是总最优操作次数。
考虑DP，对状态化简，只关注上一个1的差值
\(f[i][j]代表到i位置差值是j的方案数，g代表总操作数\)
转移分01，10，00，11，？0，？1，1？，0？，？？疯狂讨论，不难
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rint register int
#define chu printf
inline ll re() {
ll x = 0, h = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
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 mod = 1e9 + 7, N = 2100;
int f[N][N << 1], g[N][N << 1], base = 2001;
int n;
char s[N], t[N];
inline void upd(int& x, int y) {
x = x + y;
x = ((x < 0) ? (x + mod) : ((x >= mod) ? (x - mod) : x));
}
int main() {
freopen("master.in", "r", stdin);
freopen("master.out", "w", stdout);
// freopen("1.in","r",stdin);
// freope("1.out","w",stdout);
// f[x][y]:表示前x个数，sigma(a-b)=y的方案数
// g[x][y]:表示前x个数，sigma(a-b)=y的总操作数
int T = re();
while (T--) {
n = re();
scanf("%s%s", s + 1, t + 1);
for (rint i = 1; i <= n; i += 2) {
if (s[i] == '1')
s[i] = '0';
else if (s[i] == '0')
s[i] = '1';
}
for (rint i = 1; i <= n; i += 2) {
if (t[i] == '1')
t[i] = '0';
else if (t[i] == '0')
t[i] = '1';
}
f[0][base] = 1;
for (rint i = 1; i <= n; ++i) {
for (rint j = -n; j <= n; ++j) {
int J = abs(j);
j += base;
if (s[i] == t[i] && s[i] != '?') // 1 1/0 0
{
upd(f[i][j], f[i - 1][j]);
upd(g[i][j], (g[i - 1][j] + 1ll * f[i][j] * J % mod) % mod);
} else if (s[i] == '0' && t[i] == '1') {
upd(f[i][j], f[i - 1][j + 1]),
upd(g[i][j], (g[i - 1][j + 1] + 1ll * f[i][j] * J % mod) % mod);
} else if (s[i] == '1' && t[i] == '0') {
upd(f[i][j], f[i - 1][j - 1]);
upd(g[i][j], (g[i - 1][j - 1] + 1ll * f[i][j] * J % mod) % mod);
} else if ((s[i] == '1' && t[i] == '?') || (s[i] == '?' && t[i] == '0')) {
upd(f[i][j], f[i - 1][j]);
upd(g[i][j], g[i - 1][j]); // g需要更新几次啊？
upd(f[i][j], f[i - 1][j - 1]);
upd(g[i][j], g[i - 1][j - 1]);
upd(g[i][j], 1ll * f[i][j] * J % mod);
} else if ((s[i] == '0' && t[i] == '?') || (s[i] == '?' && t[i] == '1')) {
upd(f[i][j], f[i - 1][j]);
upd(g[i][j], g[i - 1][j]); // g需要更新几次啊？
upd(f[i][j], f[i - 1][j + 1]);
upd(g[i][j], g[i - 1][j + 1]);
upd(g[i][j], 1ll * f[i][j] * J % mod);
} else {
// chu("in?(upd(%d)(%d))\n",i,j-base);
upd(f[i][j], 2ll * f[i - 1][j] % mod); // 0 0 / 1 1
upd(f[i][j], f[i - 1][j + 1]); // 0 1
upd(f[i][j], f[i - 1][j - 1]);
// if(i==1&&j==1+base)chu("her!!!!!!!!11(from%d)\n",f[i-1][j-1]);
// if(i==1&&j-base==1)chu("f:%d\n",f[i][j]);
upd(g[i][j], 2ll * g[i - 1][j] % mod);
upd(g[i][j], g[i - 1][j - 1]);
upd(g[i][j], g[i - 1][j + 1]);
upd(g[i][j], 1ll * f[i][j] * J % mod);
}
j -= base;
}
}
chu("%d\n", g[n][base]);
for (rint i = 0; i <= n; ++i)
for (rint j = -n - 1; j <= n + 1; ++j) {
// chu("f[%d][%d]:%d g[]:%d\n",i,j,f[i][j+base],g[i][j+base]);
f[i][j + base] = g[i][j + base] = 0;
}
}
return 0;
}
/*
1
4
??0?
??11
3
??1
0?0
*/