构造题单

关灯

在某条道路上，有 \(n\) 盏灯排成一排，它们有的是开着的，有的是关着的。

由于天马上就要亮了，上级给了你一个任务：把所有的灯都关掉。

只不过，这些灯都比较智能，不会被轻易关掉。它们的开或关遵循如下规则：

• 每一步只能开或关一盏灯。

• 编号为 \(1\) 的灯可以随意开或关。

• 如果编号为 \(1, 2, \cdots,k-1\) 的灯都关上了了，并且编号为 \(k\) 的灯在开着，我们可以随意开或关第 \(k+1\) 盏灯。

在关灯之前，请你计算：至少要多少步才能关上所有灯？

输入格式

第 \(1\) 行一个整数 \(n\)，表示灯的个数。

第 \(2\) 行有 \(n\) 个整数，如果第 \(i\) 个整数 \(O_i=0\)，表示第 \(i\) 个盏灯初始的时候是关着的；如果 \(O_i=1\)，表示第 \(i\) 盏灯初始的时候是开着的。

输出格式

共一行一个整数，表示最少需要多少步才能关上所有灯。

• 对于 \(100\%\) 的数据，\(n \le 1000\)。

---

参考 九连环

怎么样来思考呢？我们要从子问题入手一步步解决问题。那么这里的子问题是什么？如何将0001变成0000。

直接构造可能很难，因此我们考虑dp的思路：利用之前求出的信息。于是我们已知001变成000需要的步数。

于是我们可以先让0001变成0011，再变成0010，再变成0000即可。

于是我们记为将长度为i的00..1→00..0的步数，\(c_{i,1}\)相反。于是我们可以得到c的递推式：\(c_{i,0}=c_{i,1}=c_{i-1,1}+c_{i-1,0}+1\)。显然有\(c_{0,1}=c_{0,0}=1\)。就有\(c_{i,0/1}=2^i-1\)。

我们再来考虑问题。设f_i为将前i为修改为0的代价，如果\(s_i=0\)有\(f_i=f_{i-1}\)。否则\(f_i=f_{i-1}+c_{i,0}\)。

但是这样写是错的，因为我们重复进行了无用的操作：我们要让0001变成0000，那么先要得到0011.但是上面的转移意味着我们要先得到0001，再到0011。于是我们可以直接用\(c_{i-1,0}-f_{i-1}\)替代。

则\(f_{i}=c_{i-1,0}+c_{i-1,1}+1-f_{i-1}=2^i-1-f_{i-1}\)。

Flawed Flow

现在有一个 \(N\) 个点 \(M\) 条边的无向图。它原本代表了一个网络流图，可是现在所有边的方向都丢失了，仅剩下流量。你需要给每个边规定一个方向，使得这个图成为一个合格的网络流图。

“合格”需要满足以下几个条件：

1. \(1\) 号点是源点，没有入度；N号点时汇点，没有出度。

2. \(2\) ~ \(N-1\)的每一个点，都满足入度之和等于出度之和。

3. 定向好的有向图中没有环！特别注意第三点。

现在你需要给出这样一个定向方案，如果有多个，随意给出一个合法的即可。

思路

我们记数组 \(f_i\) 表示点 \(i\) 的流量。那么当且仅当 \(f_i=0\) 时该点的收支平衡。源点和汇点的收支我们不管。

那么我们首先可以确定的就是源点出去的边的方向。

我们先假设地把每个 \(f_i\) 设置为与 \(i\) 相连的所有边的权值和（权值就是该边的流量），那么假设我们要把i的一条边改成出边，我们就把 \(f_i\) 减去两倍的其边权即可。

我们使用 bfs，先把源点加入。每一次从队列中取出一个点 \(u\)，这个点是满足收支平衡的。我们扫描 \(u\) 的邻点 \(v\) （跳过已经收支平衡的点），边为 \(e\)，边权为 \(w_e\)，如果发现 \(f_v≠0\)，那么就把 \(f_v\) 减去 \(2\times w_e\) 并且标记边 \(e\) 的方向且标记 \(e\) 已经确定了方向，下次访问时就跳过。这样做是标记边 \(e\) 从 \(v→u\)。注意，这样操作是不会影响到 \(f_u\) 的，因为原来我们的 \(f_u,f_v\) 都加了 \(2\times w_e\)，我们把其中一个点（如 \(v\)）减去 \(2\times w_e\) 就相当于一个点出一个点入，恰好人这条边合法了。如果在操作后我们发现 \(v\) 的收支平衡了，就加入队列并标记。

因为最后的图中无环、且每条边都被分配了方向，因此是 DAG，可用拓扑排序解决，所以上述的 bfs 是可以求得最终的答案的。

---

#include<bits/stdc++.h>
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
#define int long long
#define pii pair<int,int>

#define lc(x) (x<<1)
#define rc(x) (x<<1|1)

#define rd read()
int read(){
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}

const int N=2e6+15;
const int INF=1e9+5;
const int MOD=998244353;

struct edge{
    int id,to,nxt,w;
    bool d,used;
}e[N];
int tot;
int h[N];
void init(){
    tot=0;
    memset(h,-1,sizeof(h));
}
void add(int id,int u,int v,int w){
    e[tot]=(edge){id,v,h[u],w,0,1};
    h[u]=tot++;
    e[tot]=(edge){id,u,h[v],w,1,1};
    h[v]=tot++;
}
bool vis[N],ans[N];
int flow[N];
queue<int> q;
int n,m;
signed main(){
    init();
    n=rd,m=rd;
    for (int i=0;i<m;++i){

        int a=rd,b=rd,c=rd;
        add(i,a,b,c);
        flow[a]+=c;
        flow[b]+=c;
    }
    q.push(1);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=true;
        for (int i=h[u];~i;i=e[i].nxt){
            edge E=e[i];
            if (!E.used) continue;
            int v=E.to;
            if (vis[v]) continue;
            flow[v]-=2*E.w;
            ans[E.id]=E.d;
            e[i^1].used=false;
            if (!flow[v]&&v!=n)
                q.push(v);
        }
    }
    for (int i=0;i<m;++i){
        printf("%d\n",ans[i]);
    }
    return 0;
}

Koishi Loves Construction

题目描述

Koishi 决定走出幻想乡成为数学大师！

Flandre 听说她数学学的很好，就给 Koishi 出了这样一道构造题：

Task1：试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀和在模 \(n\) 的意义下互不相同。

Task2：试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀积在模 \(n\) 的意义下互不相同。

按照套路，Koishi 假装自己根本不会捉，就来找你帮忙辣。

思路 #1

试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀和在模 \(n\) 的意义下互不相同。

---

n只能是偶数或者1，因为如果n为奇数，则

\sum\limits_{i=1}^{n=1}=n(n-1)/2是n的倍数。

构造方法是对于i是奇数，则a_i=n-i+1，否则a_i=i-1。

证明

在模n意义下，若n=6，则有

0 1 -2 3 -4 5

很明显可以发现是符合要求的。

思路 #2

试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀积在模 \(n\) 的意义下互不相同。

---

我们发现a_1必须是1，a_n必须是n。并且我们可以构造模后数组为从1到n到0，例如n=6时

1 2 3 4 5 0

即\(s_{i-1}+1≡s_{i-1}\times a_i\)

则推一推后

注意到当 n 为合数时（4除外）， n∣(n−1)! ，即 s_{n−1}​≡s_{n}​(\mod n) ，无法构造出合法序列。

---

#include<bits/stdc++.h>
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
#define int long long
#define pii pair<int,int>

#define lc(x) (x<<1)
#define rc(x) (x<<1|1)

#define rd read()
int read(){
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}

const int N=2e6+15;
const int INF=1e9+5;
const int MOD=998244353;



int X,T,n;

int ksm(int a,int b,int MOD){
    int res=1;
    while(b){
        if(b&1)res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}


int inv(int x,int MOD) { 
    return ksm(x,MOD-2,MOD);
}

bool isprime(int x) {
    if(x<2)return 0;
    if(x<4)return 1;
    if(x%6!=1 && x%6!=5)return 0;
    for(int i=5,lim=sqrt(x);i<=lim;i+=6)
        if(!(x%i) || !(x%(i+2)))return 0;
    return 1;
}

void solve1(int n) {
    if((n&1) && n!=1) {
        cout<<0<<endl;
        return ;
    }
    cout<<2<<' ';
    for(int i=1;i<=n;++i)printf("%lld ",(i&1) ? (n-i+1) : (i-1)); // 带入通项公式
}

void solve2(int n) {
    if(isprime(n)) { 
        printf("2 1 ");
        int k=1;
        for(int i=2;i<n;++i) {
            printf("%lld ",inv(k,n)+1);
            k=k*((inv(k,n)+1)%n)%n; // 递推a[i]
        }
        if(n>1)printf("%lld\n",n);
    }
    else if(n==4)puts("2 1 3 2 4");
    else puts("0");
}

signed main() {
    X=rd,T=rd;
    while(T--){
        n=rd;
        if(X==1)solve1(n);
        else solve2(n);
    }
    return 0;
}

Vladik and fractions

题面翻译

题目描述 请找出一组合法的解使得\(\frac {1}{x} + \frac{1}{y} + \frac {1}{z} = \frac {2}{n}\)成立 其中\(x,y,z\)为正整数并且互不相同

输入 一个整数\(n \(**输出** 一组合法的解\)x, y ,z\),用空格隔开 若不存在合法的解，输出\(-1\)

数据范围 对于\(100\)%的数据满足\(n \leq 10^4 \(要求答案中\)x,y,z \leq 2* 10^{9}\)

感谢@Michael_Bryant 提供的翻译

思路

设x=n,y=n+1，解得z=n(n+1)

---

代码已交

[POI2011] LIZ-Lollipop

题目描述

给一个只有 \(1\) 和 \(2\) 的序列，每次询问有没有一个子串的和为 \(x\)。W代表1，T代表2.输出任意一个满足条件的区间。

思路

离线+双指针？好像会被卡。

离线是正确的，不过我们应该从大到小，并且也不是枚举询问——而是考虑最大的可以被表示出的奇数和偶数。

设最大的可以被表示出的奇数为z，想一想，发现z-2一定可以表示，z-4也想，以此类推。偶数也一样。

那么现在我们只需要求出最大的可以被表示出的奇数和偶数就可以了。

• 若[1,n]和为奇数。那么我们找到从左往右第一个1，把它和之前的数字都删掉。或者我们找到从右往左第一个1，把它和之后的数字都删掉。取最大值即可得到最大的偶数。

• 反之亦然。

然后对于每一个x都预处理出其答案即可。

---

[AGC032B] Balanced Neighbors

题面翻译

【题目描述】

给定整数 \(N\)，构造一个从 \(1\) 到 \(N\) 编号的 \(N\) 个节点的无向图，使得：

• 该图不含有重边和自环，并且是连通的。

• 每个节点的所有邻接节点的编号之和相同。

可以证明这样的图一定存在。

【输入格式】

一行一个整数 \(N\)。

【输出格式】

第一行一个整数 \(M\)，表示构造出的图的边数。

接下来 \(M\) 行，每行两个整数 \(a_i,b_i\)，表示第 \(i\) 条边的两个端点。

如果有多种可能的构造，输出其中的任意一种即可。

【数据范围】

\(3 \leq N \leq 100\)。

【样例解释】

对于所有节点，其邻接节点的编号之和均为 \(3\)。

思路

题目要求每个节点的所有邻接节点的编号之和sum相同，那么我们先不考虑先兆，我们知道假设一个点和所有点都连边（包括它自己）那么是符合要求的。就相当于每个点的sum都等于1+2+\dots+n。那么现在我们先把自己去掉，剩下的还要去掉一个点才行。我们考虑到去掉另外一个点会影响那个点的答案，所以我们考虑构造去掉的那些边

即考虑生成一个图满足以下条件：

• 不连通

• 存在某个整数 S，对于任意的顶点，**该顶点**与该顶点邻接的顶点的编号的值的和为 S。

很显然就是n 为奇数时，连边 (1,n−1),(2,n−2),\dots

---

以下是std：

考虑生成一个图满足以下条件：

• 不连通

• 存在某个整数 S，对于任意的顶点，**该顶点**与该顶点邻接的顶点的编号的值的和为 S。

显然这个图的补图满足：

• 连通图

• 存在某个整数 S，对于任意的顶点，与该顶点邻接的顶点的编号的值的和为 S。

于是我们构造这样一个图输出其补图即可。

随手构造一下：

• n 为奇数，连边 (1,n−1),(2,n−2),…，每个顶点及邻点的编号和为 n。

• n 为偶数，连边 (1,n),(2,n−1),…，每个顶点及邻点的编号和为 n+1。

---

代码已交