BUPT 2022 Summer Training #1(2018 ICPC Asia Singapore Regional)

  A B C D E F G H I J K L
考场过题 O O O     O O      O   O
赛后补题       O             O  

Trainint4全赛总结：多开题，多开题！开的题有思路就要又快又准地做出来！没思路就不要卡着，看另一题！

A - Largest Triangle

题目大意：给定二维平面N个点，使用其中三个点得到最大三角形面积。

数据范围：3<=N<=5000,0<=x,y<=4e7（可能有重复点）

解题思路：旋转卡壳（模板）

赛后总结：A题是一道旋转卡壳模板，我随便找了个板子就用了，没深入理解，然后就WA了很多发，本质原因都是对板子的理解不够细致，比如排序时的第二关键字、叉积的顺序，凸包的构建等。

罚时情况：4次。对旋转卡壳理解不够深刻，板子敲的太少了。主要是在 重复点与构建凸包、重复点与旋转卡壳、叉积顺序、点排序预处理的第二关键（向量长度）字没处理好。

参考代码：

查看代码 
 #include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=5010;
struct Point
{
    long long x,y;
}P[N],Stack[N];
int n,top;
long long cross(const Point&a,const Point&b,const Point&c)
{
    //x1y2-x2y1;
    long long x1=a.x-c.x;
    long long x2=b.x-c.x;
    long long y1=a.y-c.y;
    long long y2=b.y-c.y;
    return x1*y2-x2*y1;
}
long long len(const Point&a,const Point&b)
{
    long long x=a.x-b.x;
    long long y=a.y-b.y;
    return x*x+y*y;
}
int cmp(const Point&a,const Point&b)
{
    long long tmp=cross(a,b,P[1]);
    if (tmp!=0) return tmp>0;
    return len(a,P[1])1) top--;
        //要注意重复点的取出，如果叉积=0也要从栈顶弹出 
        Stack[++top]=P[i];
    }//把最后一个点也放入凸包，保证凸包正确性
    long long ans=0;
    For(i,1,top) 
    {
        int now=i;
        For(j,i+1,top) if (P[i].x!=P[j].x||P[i].y!=P[j].y)
        {
            int cnt=0;
            while (cross(Stack[j],Stack[now%top+1],Stack[i])>=cross(Stack[j],Stack[now],Stack[i])) 
            {
                cnt++;if (cnt>top) break;
                now=now%top+1;
            }
            ans=std::max(ans,cross(Stack[j],Stack[now],Stack[i]));
        }    
    }
    printf("%.8lf\n",ans/2.0);
    return 0;
}

B - Hoppers

题目大意：给定一张N个点M条边无向图，可以选定一个点染色，随后距离被染色的距离为2的点都会被染色。求至少需要向图中添加几条边使得选定一个点染色后可以将整个图染色。

数据范围：3<=N<=5e5,2<=M<=5e5

解题思路：

先将题意转化一下，将这个图拆成上下两层，当前点第1/2层可以和相邻的点第2/1层的连边，也就是说当前点可以隔一个点到达相同层的另一个点，要将整个图染色实际上是要把同一层的所有点染色。

1、先考察一个连通块的情况：由于是一个连通块，那么可以把这个图中某一个点到达其他点的情况可以看作鸡蛋的包装壳，形如：^^vv^^v^^^^v

一旦某个点拆出的上下两个点可互相到达，那么这个连通块必定可以整个染色（实际上就是在二分图中这个点有一个点既被染成白色又被染成黑色）

如果不存在这种的，那么只需要让某个点A的第1/2层向距离为2的某个点B的第2/1层连边，由于在这之前A的第1/2层经过中间点C的2/1层已经和B的1/2层相连，因此B的1、2层可互相到达

综上，如果一个图中某个点可同时被染成黑色和白色，则这个图合法，如果不行则加一条边即可合法

2、再考虑多个连通块的情况：如果一个合法的连通图中的某个点A加一条边到另外一个不合法的连通图的点B，由于A的上下两层互相可达，那么A的1/2层连向B的2/1层后，B的上下两层也互相可达，即新的连通图合法

3、综上，答案为(连通块数量-1)+(存在合法连通块?0:1)

赛后总结：一道不错的思维题。

罚时情况：无罚时。

参考代码：

查看代码 
 #include
#include
#include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=5e5+1000;
std::vector To[N];
int vis[N],from[N];
int BFS(int st)
{
    int OK=0;
    std::queue Q;
    Q.push(st);vis[st]=1;
    while(!Q.empty() )
    {
        int u=Q.front() ;Q.pop() ;
        For(i,0,(int)To[u].size()-1)
        {
            if (!vis[To[u][i]]) 
            {
                from[To[u][i]]=u;
                vis[To[u][i]]=vis[u]%2+1;
                Q.push(To[u][i]); 
            }
            else 
            {
                if (To[u][i]!=from[u]&&vis[u]==vis[To[u][i]]) OK=1;
            }
        } 
    }
    return OK;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    For(i,1,m) 
    {
        int u,v;
        scanf("%d%d",&u,&v);
        To[u].push_back(v);
        To[v].push_back(u);  
    }
    int ans=0,OK=0;
    For(i,1,n) if (!vis[i])
    {
        OK|=BFS(i);
        ans++;
    }
    printf("%d\n",ans-OK);
    return 0;
}

C - SG Coin

题目背景：Alice以SGcoin为货币向Bob购买东西，交易被记录在区块链中，区块链中的每一块包含前一块的哈希值、交易字符串、令牌、当前块的哈希值。

令牌的值为0~1e9-1，哈希值有7个尾0。

在分布式系统中区块链会进行广播，每个人会根据收到的最长链在后面加一个新的块，每个人都可以都可以判断是否合法（最后一块的哈希值+交易字符串+令牌->新块的哈希值）。

Charlie要通过快速产生新块从而产生最长链来攻击分布式区块链系统。比如拦截消费方的区块链，产生新的最长链并广播，让供应方拒收正常的更短的区块链。

题目大意：给定哈希算法，要求根据给定的最后一块的哈希值，快速产生2个新块（任意交易字符串+0~1e9-1的令牌值）。注意，产生的新块的末尾必须有7个0。

数据范围：0

解题思路：随便选个字符串模拟，最后通过令牌值把哈希值调整到末尾有7个0（%1e7==0）（由于不知道能否为8个0，如果）

罚时原因：1次。队友做的，不知道

参考代码：

查看代码 
 /*#if(__cplusplus == 201103L)
#include 
#include 
#else
#include 
#include 
namespace std
{
    using std::tr1::unordered_map;
    using std::tr1::unordered_set;
}
#endif*/
#include
using namespace std;
long long pre,mod=1e9+7,kmod=1e7,token,pmod=1e8,tem;
string s="aa";
int main()
{
    cin>>pre;
    int len=s.size();
    long long v=pre;
    for(int i=0;i

D - Bitwise

题目大意：n个数组成一个环，要求将这n个数分成恰好k个非空段，使得每一段的"按位或"后的值再进行"按位与"之后最大

数据范围：1<=K<=N<=5e5,0<=Ai<=1e9

解题思路：

首先很容易想到的是从高位到低位贪心，如果check(ans|(1<

那么关键问题是如何判断能否让序列分成K段，每一段按位或以后包含X，即check(X)=true呢？

方法一：暴力，枚举第一段的起点位置，复杂度O(logn*n^2)

方法二：优化暴力，枚举最后一段（一部分在头一部分在尾的那一段）终点。

参考链接：http://www.latenightcode.xyz/blog/13_bits

由于任何一种满足题意的分段方案一定能通过把最后一段的结束位置尽可能提前（保证按位或后仍包含X），从而使得最后一段的结束位置的某一位1在最后一段中第一次出现，且由于最后一段还包含的本序列的末尾部分，因此这一位1一定也是在序列中第一次出现，所以只需要枚举每位1第一次出现的位置为最后一段的结束位置即可。

复杂度O(logn*logn*n)

方法三：不枚举起点，通过把n个数复制一份接在后面，做成一个双倍环，从而做到同时考虑所有起点的情况。（很有意思的trick!）

若该环最多可以凑出k段，则一个双倍的环可以凑出2k段，该双倍环剪开形成的带至少可以凑出2k-1段（最后一段可能被剪开，但这一段实际上已经在双倍环中间有算过一次了）

如果该环最多凑出<=k-1段，则双倍环最多凑出<=2k-2段，该双倍环剪开形成的带最多也就2k-2段

 注意：双倍环分出的段数要>=2k-1才能保证原环能分出k段，双倍环能分出k段不保证原环也能分出k段！

复杂度O(logn*n)  AC!

罚时情况：赛时没做出来

参考代码：

查看代码 
 #include 
#include 
#include 
using namespace std;
const int N = 1e6+10;
int n,k;
int a[N];
int pos[40];
bool check(int x){
    int cur=0;
    int now=0;
    for(int j=0;j<2*n;j++){
        now|=a[j];
        if((now&x)==x){
            now=0;
            cur++;
        }
    }
    return cur>=2*k-1;
        
}
int main()
{
    scanf("%d%d",&n,&k);
    memset(pos,0x3f,sizeof pos);
    for(int i=0;i=0;i--){
        if(check(ans|(1<

F - Wi Know

题目大意：给定一个大小为N的数组S，求字典序最小的(A, B)，A≠B，使得数组中存在形如 ABAB 的子序列（不需连续）。

数据范围：4<=N<=4e5,1<=Si<=N

解题思路：

区间修改，单点查询：

从左往右和从右往左扫，记录每个元素的第一个位置、最后一个位置、后一个相同元素位置、前一个相同元素位置。记ABAB为A1 B1 A2 B2

写一颗线段树，线段树的每个叶子存当前这个点作为A2时的可匹配的B（B1在A2前，B2在A2后）的最大的B1位置。

然后先扫一遍如果位置i后面还有相同元素就让位置i作为B1,下一个相同元素的位置next[v[i]]作为B2，中间的所有位置都可作为A2（B2不取last_pos[v[i]]是为了让A2!=B）（A2一定位于某一对最近的B1B2之间，故结果肯定正确），让这些A2更新一下他前面最大的可匹配的B1位置，即区间更新最大值。

然后再扫一遍数组，看哪些位置可以作为A，如果最大的B1位置（单点查询）在first_pos[v[i]]之后则当前这个位置i可以作为A，对所有可取的A取最小。

为了保证字典序最小，在确定了最小的A以后要再重新确定B。

只要再扫一遍数组，枚举哪个位置的数作为B1是合法的，即当前B1前面有A可以作为A1，当前B1后面也有A可以作为A2，且A2在last_pos[v[i]]之前。

取一个最小的B就可以得到字典序最小的ABAB了。

（其实也可 单点修改，区间查询，每个[l,l]的叶子只记录last_pos[v[l]]即可，区间[pre[i]+1,i-1]（不取first_pos是为了让A!=B）查询这些位置是否可作为B，即的最大的last_pos[]是否大于i即可）(由于B必定位于某一对最近的A之间，故结果肯定正确）

赛后总结：考场明明写出来了交上去却RE，千万不要写成return printf();！！！要写return  printf(),0;！！不要再犯了！！

这题本质上其实是在每个位置多存了一个由特殊含义的数组，把匹配信息A1A2/B1B2隐藏在数组中，然后再用线段树维护这个数组，并去匹配B1B2/A1A2，从而做到A1B1A2B2

罚时原因：RE，main函数写return printf();导致没有返回0

参考代码：

查看代码 
 #include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Frd(i,a,b) for(int i=a;i>=b;i--)
const int N=4e5+1000;
int v[N],pos[N],first_pos[N],last_pos[N],Next[N],Pre[N],sum[N];
int max[4*N];
void update(int root,int l,int r,int a,int b,int x)
{
    if (l==a&&r==b) 
    {
        max[root]=std::max(max[root],x);
        return ;
    }
    int mid=(l+r)>>1;
    if (b<=mid) update(root<<1,l,mid,a,b,x);
    else 
    {
        if (a>mid) update(root<<1|1,mid+1,r,a,b,x);
        else update(root<<1,l,mid,a,mid,x),update(root<<1|1,mid+1,r,mid+1,b,x);
    }
}
int query(int root,int l,int r,int x)
{
    if (l==r) return max[root];
    int mid=(l+r)>>1;
    if (x<=mid) return std::max(max[root],query(root<<1,l,mid,x));
    else return std::max(max[root],query(root<<1|1,mid+1,r,x));
}
int main()
{
    int n;scanf("%d",&n);
    For(i,1,n) scanf("%d",&v[i]);
    For(i,1,n) pos[i]=0;
    Frd(i,n,1) 
    {
        if (pos[v[i]]) Next[i]=pos[v[i]];
        pos[v[i]]=i;
        if (!last_pos[v[i]]) last_pos[v[i]]=i;
    }
    For(i,1,n) pos[i]=0;
    For(i,1,n) 
    {
        if (pos[v[i]]) Pre[i]=pos[v[i]];
        pos[v[i]]=i;
        if (!first_pos[v[i]]) first_pos[v[i]]=i;
    }
    
    For(i,1,n) if (Next[i]&&i+1<=Next[i]-1) update(1,1,n,i+1,Next[i]-1,i);
    int A=n+1;
    For(i,1,n)  if (i!=first_pos[v[i]]&&query(1,1,n,i)>first_pos[v[i]]) 
        A=std::min(A,v[i]);
    if (A==n+1) return printf("%d\n",-1),0;
    For(i,1,n) sum[i]=sum[i-1]+(v[i]==A);
    int B=n+1;
    For(i,1,n) 
    {
//        printf("%d %d %d %d\n",i,last_pos[v[i]],sum[i-1],sum[last_pos[v[i]]-1]-sum[i]);
        if (v[i]!=A&&i!=last_pos[v[i]]&&sum[i-1]&&sum[last_pos[v[i]]-1]-sum[i]) B=std::min(B,v[i]);
    }
    printf("%d %d\n",A,B);
    return 0; 
}

G - Rectangular City

题目大意：给定R*C的矩阵，要求选出N个子矩阵使得这些矩阵的交的面积不小于N，求方案数。

数据范围：1<=N<=1e6,1<=R,C<=5000,1<=K<=R*C

解题思路：

首先发现矩形和矩形的交必定还是矩形，因此只需要枚举最终交集矩形的长和宽即可。

然后可以发现行和列是独立的，所以可以分开成两个一维问题处理：在一个长为L的线段中选出n个子线段使得这些线段的交的长度==t。

通过枚举最终交集线段左端点位置来计算交集线段长度==t的方案数。

如果确定最终交集线段左端点和右端点位置已确定，那么这n个线段的的左端点有a种选择，线段的右端点有b种选择，另外还需要保证线段的交的长度==t而不是>=t（>=t会导致最终计算答案是重复计算）

那么可以得出方案数为(an-(a-1)n)(bn-(b-1)n);

(an?(a?1)n)表示保证最终的左端点必须为某个特定位置（至少得有一个线段的左端点和最终交集线段的左端点相同），最终最后合并两个一维问题的答案即可。

赛后总结：分析出行列互相独立是最重要的一步，丁老师TQL，另外去重也很重要就是了。

罚时原因：一开始没想到简便的去重方法，TLE。

参考代码：

查看代码 
 #include
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
const int RC=5010;
const long long mod=1e9+7;
long long powern[RC],cnt[RC][2],n,r,c,k,ans;
long long power(long long x,long long y)
{
	long long ans=1;
	while (y)
	{
		if (y&1) ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ans;
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&r,&c,&k);
	For(i,1,5000) powern[i]=power(i,n);
	For(x,1,r) For(i,1,r-x+1) cnt[x][0]=(cnt[x][0]+(powern[i]-powern[i-1]+mod)*(powern[r-x+2-i]-powern[r-x+2-i-1]+mod)%mod)%mod;
	For(x,1,c) For(i,1,c-x+1) cnt[x][1]=(cnt[x][1]+(powern[i]-powern[i-1]+mod)*(powern[c-x+2-i]-powern[c-x+2-i-1]+mod)%mod)%mod;
//						printf("?? %d %d %lld %lld\n ",x,i,(powern[i]-powern[0]),(powern[c-x+2-i]-powern[c-x+2-i-1]));
	For(i,1,r) For(j,1,c) if (i*j>=k) ans=(ans+cnt[i][0]*cnt[j][1]%mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

J - Free Food

签到题。队友做的，不了解

罚时情况：无罚时。

参考代码：

查看代码 
 #include 
#include 
#include 
using namespace std;
const int N = 400;
bool a[N];
int main()
{
    int n;
    cin>>n;
    while(n--){
        int l,r;
        cin>>l>>r;
        for(int i=l;i<=r;i++)a[i]=1;
    }
    int k=0;
    for(int i=0;i<399;i++)if(a[i])k++;
    cout<

K - Conveyor Belts

题目大意：

N个点，M条边的有向图，可有重边和自环。

前K个点中，编号为j(1<=j<=K)的点会在第(x*K+j)(x>=0)分钟产生物品。物品被产生后立刻送往第N个点（如果在第N个点产生就不用）

相同点j(1<=j<=K)产生的所有物品到达点N的路径必须相同。

M条边每条边耗时1min，忽略点内耗时。

请问最多留下多少个点产生物品，满足每个物品能送到点N，且每条边每分钟最多运输1个物品？

数据范围：1<=K<=N<=300,0<=M<=1000

解题思路：最大流。

对每个节点拆分成K个节点，表示每个节点在第i分钟的情况，若某条边连接x和y，则对x的第i分钟与y的第i+1分钟建立一条权值为1的边（若i=K则对x的第K分钟与y的第1分钟建边），源点对于前K个节点的产出物品时间建立权值为1的边，对节点N的所有分钟建立流向汇点权值为inf的边。（一定要是inf，因为仓库是可以两个及以上的物品同时到达）接着跑最大流即可。

补充知识：Dinic算法的复杂度分析及证明

1、一般图的Dinic时间复杂度：O(n*nm)：

（1）bfs：最多建n次分层图（残留网络中s->t的最短路长度必定增加，因为所有走最短路的流都被dfs跑完了）

（2）dfs：①增广在每次分层图中最多执行m次dfs（每次dfs产生的流必定=路径上最小边的容量），一次dfs最多走n个点（分层图）,所有dfs总复杂度O(nm)

????    ②增广时非可行边产生的代价：由于当前弧优化，不可行的边只会走一次，所有dfs总复杂度O(m)

??????（相对于①该复杂度可忽略，如果不加弧优化那么m次dfs的总复杂度可能到O(m2)）

综上，Dinic时间复杂度O(n*nm)（无弧优化的时间复杂度为O(n*m2)）

2、单位图的Dinic时间复杂度：O(n1/2*nm)

单位图(unit graph) 是指，所有的边的容量都是整数，且每一个不是s或t的点，要么出度为1，连出去的边容量为1，要么入度为1，连进来的边容量为1。

3、边的容量为1的图的Dinic时间复杂度：O(min{n2/3,m1/2} *nm)

赛后总结：赛时知道是网络流，思路其实也差不多出来了，但是感觉有问题（也有时间原因）就没再往下想下去。

罚时原因：赛时没做出来。

参考代码：

查看代码 
 #include
#include
#include
#define INF 0x3f3f3f3f
#define ST (n*k+1)
#define ED (n*k+2) 
#define For(i,a,b) for(int i=a;i<=b;i++)
#include
const int N=300*300+2+1000;
const int M=2*(300+300+1000*300)+10000;
int n,k,m; 
int id(int x,int min)
{
	return (x-1)*k+min;
}
struct Edge
{
	int to,cap,next;
}e[M];int e_cnt;
int Head[N]; 
void Link(int a,int b,int c)
{
	e[e_cnt]=(Edge){b,c,Head[a]};
	Head[a]=e_cnt;
	e_cnt++;
	e[e_cnt]=(Edge){a,0,Head[b]};
	Head[b]=e_cnt;
	e_cnt++;
}
std::queue Q;int high[N];
int BFS()
{
	memset(high,0,sizeof(high));
	Q.push(ST);high[ST]=1;
	while (!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int p=Head[u];p!=-1;p=e[p].next ) if (e[p].cap >0&&!high[e[p].to ])
			high[e[p].to]=high[u]+1,Q.push(e[p].to);
	}
	return high[ED]!=0;
}
int cur[N];
int dfs(int now,int cap)
{
	if (now==ED) return cap;
	if (!cap) return 0;
	for(int &p=cur[now];p!=-1;p=e[p].next) if (high[e[p].to]==high[now]+1&&e[p].cap>0)
	{
		int flow=dfs(e[p].to,std::min(cap,e[p].cap));
		if (flow>0)
		{
			e[p].cap-=flow;
			e[p^1].cap+=flow;
			return flow;
		}
	}
	return 0;
}
int Dinic()
{
	int ans=0;
	while (BFS())
	{
		int flow=0;
		For(i,1,ED) cur[i]=Head[i];
		while (flow=dfs(ST,INF)) ans+=flow;
	}
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	memset(Head,-1,sizeof(Head));
	For(i,1,k) Link(ST,id(i,i),1);//可产生物品的点
	For(i,1,k) Link(id(n,i),ED,INF); //终点在任意时间接收任意数量物品
	For(i,1,m)
	{
		int a,b;scanf("%d%d",&a,&b);
		For(j,1,k) Link(id(a,j),id(b,j%k+1),1); //注意j%k+1
	}
	printf("%d\n",Dinic());
	return 0;
 }

L - Non-Prime Factors

题目大意：Q个询问，每次询问i的非质数因子的个数

数据范围：1<=Q<=3e6,2<=i<=2e6

解题思路：先nlogn求出所有数i的因子个数（含1和i），再线性筛一下求出所有数i的质数因子个数，两个一减答案就出来了。

罚时情况：无罚时。

参考代码：

查看代码 
 #include 
#include 
#include 
using namespace std;
const int N = 2e6+10;
int a[N];
int prime[N],cnt;
bool st[N];
int b[N];
int q;
int main()
{
    for(int i=1;i
ACM系列二分图染色旋转卡壳双倍环最大流质数筛组合计数线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

P5736 质数筛

cf739 C. Alyona and towers（线段树）

可持久化线段树

标签

一品网 冀ICP备14022925号-6