Codeforces Round #558 (Div. 2)

文章目录

Codeforces Round #558 (Div. 2)

退役打cf第一场

A - Eating Soup

注意考虑全面即可

int a,b;cin>>a>>b;
    if(b == 0)
    	cout<<1<<endl;
    else if(b < (a+1)/2 )
    	cout<<b<<endl;
    else
    	cout<<a-b<<endl;

B- Cat Party

分类讨论即可

num[i] 代表值为i的有多少个
ma[num[i]] 代表数量为num[i] 的有多少个
注意维护他们两个就OK了
ma的size大于等于3肯定不可以
ma的size<mark>1 ，必须是first为1,或者second为1
ma的size</mark>2，如果都是数量为1，肯定可以
如果有一个数量为1，可以直接删除
否则只能是连续的，删除数量多的那一个

const int maxn = 1e5+10;
int num[maxn];
int main(void)
{
	int n;cin>>n;
	int ans = 1;
	map<int,int> ma;
	for(int i = 1;i <= n; ++i){
		int a;scanf("%d",&a);
		if(num[a] != 0)
			ma[num[a]]--;
		if(ma[num[a]] == 0) 
			ma.erase(num[a]);
		num[a]++;
		ma[num[a]]++;
		if(ma.size() >= 3) continue;
		if(ma.size() ==1){
			P p = *ma.begin();
			if(p.second == 1) ans = i;
			if(p.first == 1) ans = i;
			continue;
		}
		if(ma.size() == 2){
			auto c = ma.begin();
			P p1 = *c;c++;
			P p2 = *c;
			if(p1.first == 1&&p1.second == 1) 
				ans = i;
			if(p2.first == 1&&p2.second == 1)
				ans = i;
			if(p2.first == p1.first + 1&&p2.second == 1)
				ans = i;

		}
	}
	cout<<ans<<endl;   
   return 0;
}

C2 - Power Transmission (Hard Edition)

O ( n 2 ) O(n^2) O(n2) 枚举直线，如果有和之前的重合，就舍去，如果有重合，说明至少三个点，暴力枚举第二个点即可
用pair类型存储直线的斜率有关信息，把相同斜率的存到map里面，平行的舍去，其它的相交

const int maxn = 2500*2500+10;
int x[maxn],y[maxn];
int main(void)
{

    int n;cin>>n;
    LL ans = 0;
    map<Line,LL> ma;
    map<P,int> maa;
    LL num = 0;
    for(int i = 1;i <= n; ++i)
    	{
    		scanf("%d%d",&x[i],&y[i]);
    		for(int j = 1;j < i; ++j){
    			 Line L = Line{x[i],y[i],x[j],y[j]};
    			 P p = P(x[i]-x[j],y[i]-y[j]);
    			 int d = gcd(p.FI,p.SE);
    			 p.FI /= d;
    			 p.SE /= d;
    			 if(p.FI < 0)
    			 	p.FI *= -1,p.SE *= -1;
    			bool yes = true;
    			for(int k = 1;k < i; ++k){
    				if(j == k) continue;
    				// Line L = Line{x[i],y[i],x[j],y[j]};
    				Line L2 = Line{x[j],y[j],x[k],y[k]};
    				// if(j == 2&&k == 1&&i == 3){
    				// cout<<(L == L2)<<endl; 
    				// }
    				if(L == L2){

    					yes = false;
    					break;

    				}
    			}
    			if(!yes) continue;
    			ans += num-maa[p];
    			maa[p]++;
    			num++;
    		}
    		// cout<<"i = "<<i<<" "<<num<<endl;
    	}
    // cout<<num<<endl;
   cout<<ans<<endl;
   return 0;
}

D - Mysterious Code

题意：给定一个c作为母串，s，t作为匹配串，其中c有一些字母不确定，定义 f ( s 1 , s 2 ) f(s1,s2) f(s1,s2) 为s2在s1 中出现的次数，求 m a x ( f ( c , s ) − f ( c , t ) ) max(f(c,s)-f(c,t)) max(f(c,s)−f(c,t))

分析：kmp+我为人人递推型dp，非常常见的套路
f [ i ] [ j ] [ k ] 代 表 到 了 第 i 个 字 符 ， 应 该 匹 配 s 的 第 j 个 ， 应 该 匹 配 t 的 第 k 个 ， 最 大 差 是 多 少 f[i][j][k] 代表到了第i个字符，应该匹配s的第j个，应该匹配t的第k个，最大差是多少 f[i][j][k]代表到了第i个字符，应该匹配s的第j个，应该匹配t的第k个，最大差是多少
现在的转态是 i , j , k i,j,k i,j,k 根据fail指针求出下一个 f [ i + 1 ] [ j j ] [ k k ] f[i+1][jj][kk] f[i+1][jj][kk]

;
const int maxn = 1000+10;
char c[maxn],s[maxn],t[maxn];
void getFail(char *P,int *f)
{
    int m = strlen(P);
    f[0] = 0,f[1] = 0;
    for(int i = 1;i < m; ++i)
    {
        int j = f[i];
        while(j && P[i] != P[j]) j = f[j];
        f[i+1] = P[i] == P[j] ? j + 1: 0;

    }

}
inline void  chkmax(int &a,int b){
	a = a<b?b:a;
}
const int maxm = 60;
int f[maxn][maxm][maxm];
int fs[maxm],ft[maxm];
int main(void)
{
	// memset(f,-1,sizeof(f));
    
    cin>>c>>s>>t;
    int nc = strlen(c);
    int ns = strlen(s);
    int nt = strlen(t);
    // cout<<nc<<" "<<ns<"'
    getFail(s,fs);
    getFail(t,ft);
    for(int i = 0;i <= nc; ++i)
    	for(int j = 0;j<= ns; ++j)
    		for(int k =0;k <= nt; ++k)
    			f[i][j][k] = -INF;
    f[0][0][0] = 0;
    int ans = -INF;
    for(int i = 0;i < nc;++i){
    	for(char ch = 'a';ch <= 'z'; ++ch){
    		if(c[i] !='*'&&c[i]!=ch) continue;

    		for(int  j = 0;j <= ns; ++j){
	    		for(int  k = 0;k <= nt; ++k){
	    			if(f[i][j][k] == -INF) continue;
	    			int jj = j;
	    			int kk = k;
	    			while(jj&&ch != s[jj])jj = fs[jj];
	    			while(kk&&ch != t[kk])kk = ft[kk];
	    			if(ch == s[jj]) jj++;
	    			if(ch == t[kk]) kk++;
	    			int t= 0;
	    			if(jj==ns)
	    				t++;
	    			if(kk==nt)
	    				t--;
	    			// cout<<t<<endl;
	    			// int &F = f[i]
	    			// if(t >= 1){
	    			// cout<<i<<endl;
	    			// }
	    			chkmax(f[i+1][jj][kk],f[i][j][k]+t);
	    			// f[i+1][jj][kk] = max()
	    		}
    		}
    	}
    }
    for(int j = 0;j <=ns; ++j)
    	for(int k = 0;k <= nt; ++k)
    		chkmax(ans,f[nc][j][k]);
    // for(int j = 0;j <= ns; ++j){
    // for(int k = 0;k <= nt; ++k){
    // cout<<setw(5)<<f[nc][j][k]<<" ";
    // }
    // cout<<endl;
    // }
    // getFail(ch,f);
    // printf("%d",f[strlen(ch)-1]);
    cout<<ans<<endl;
    return 0;
}

//f[i][j][k] 代表到了第i个，s要匹配到j，t要匹配k，最大的f(i)-f(j)


/* wcfteosuhqfgokvuctvnpiiudq**ephyfyjzitxsxedsuxwlrwqwctphp*xfkfceghepmgheqazdziqjqphdtc*bryobgqzuzouoqzfcfizbiayvcryyfqsfqzwzdhmexgdmr*fvwlpuogxcpqvvzwdvhvnc*rvkllcujibmregytsyps*zvumiklue*oimvjfqshacizmdxzrupqylcjzom dxfzbdrelqidmbkgqjsobqtjqoar vbtbkqfvprnobfpbdqpomudockgjunicbu */

E - Magical Permutation

题意：给定n个数，问能构造出来的最长的 [ 0 , 2 x − 1 ] [0,2^x-1] [0,2x−1] 的排列，这个排列相邻两个元素的异或都在n个数里面
分析：
重点1：因为排列中有0的存在，所以 [ 0 , 2 x − 1 ] [0,2^x-1] [0,2x−1] 的所有元素都能通过s集合中的元素两两异或出来
重点2：怎么判定最大的x呢，线性基基底数如果等于x，就一定能组合成 [ 0 , 2 x − 1 ] [0,2^x-1] [0,2x−1] 中的所有元素，从大到小暴力枚举x即可
重点3：怎么构造？
其实就是枚举这x个构成线性基的数的线性组合，那自然数的二进制不正好是吗？
所以我们从小到大枚举这个组合即可

const int MN=60;
const int maxn = 2e5+10;
int b[maxn];
LL a[61],tmp[61];
bool flag;
bool  ins(LL x){
    for(reg int i=MN;~i;i--)
        if(x&(1LL<<i))
            if(!a[i]){a[i]=x;return true;}
            else x^=a[i];
    flag=true;
    return false;
}
bool check(LL x){
    for(reg int i=MN;~i;i--)
        if(x&(1LL<<i))
            if(!a[i])return false;
            else x^=a[i];
    return true;
}
LL qmax(LL res=0){
    for(reg int i=MN;~i;i--)
        res=max(res,res^a[i]);
    return res;
}
LL qmin(){
    if(flag)return 0;
    for(reg int i=0;i<=MN;i++)
        if(a[i])return a[i];
}
LL query(LL k){
    reg LL res=0;reg int cnt=0;
    k-=flag;if(!k)return 0;
    for(reg int i=0;i<=MN;i++){
        for(int j=i-1;~j;j--)
            if(a[i]&(1LL<<j))a[i]^=a[j];
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1LL<<cnt))return -1;
    for(reg int i=0;i<cnt;i++)
        if(k&(1LL<<i))res^=tmp[i];
    return res;
}
int n;
int vec[maxn];
void check(int x){
	memset(a,0,sizeof(a));
	int cnt = 0;
	for(int i = 1;i <= n; ++i){
		if(b[i] <(1<<x)&&ins(b[i]))
			vec[cnt++] = b[i];
	}
	if(cnt != x) return ;
	// for(int i = 0;i < cnt; ++i)
	// cout<<vec[i]<<endl;
	int now = 0;
	cout<<x<<endl;
	cout<<now<<" ";
	for(int i = 0;i < (1<<x); ++i){
		for(int j = 0;j < x; ++j)
			if((i>>j)&1)
			{
				now ^= vec[j];
				cout<<now<<" ";
				break;
			}
	}
	exit(0);
}
int main(){
   	LL x;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    //,ins(x);9
    for(int i = 22;i >= 0; --i)
    	check(i);
    // printf("%lld\n",qmax());
    return 0;
}

F - Indecisive Taxi Fee

CF1164F
题意

给定一个无向图，n个点，m条边及其权值，每次修改一条边的权值，询问相互独立，对于每次询问输出从1到n的最短路
分析

最短路树+线段树优化查询

1 先从1跑单源最短路dforward，在从n跑单源最短路dbackward

2 剥离出来任意一条从1到n的最短路，并对路径上的点进行编号
结论：

  1. 如果修改的边不再最短路上，那么最短路只有两种可能，1原来的最短路，2 经过u->v 的最短路，这两者取小即可
  2. 如果修改的边在最短路上
    如果是减小，那么肯定还是这条路
    如果是增大，那么可能还是这条路，或者不经过这条边的其它最短路
    本题最重要的是求不经过某条边的最短路，怎么来求呢，我们需要知道什么是最短路树，我们从1跑单源最短路的时候就求得了最短路树，即n个点，n-1(假设都能到达)条边的树，1到每一个点的路径都是唯一的，这可以通过，每次更新的时候标记前驱节点来实现，如果一条边不在最短路上，那么他肯定与原来的最短路树形成了环，那么它就可能对这条环上的节点最短路产生贡献，我们需要对所有点进行分层，按照最短路的位置分层即每个点的层就是离他最近的最短路上的点的层数，可以通过一遍dfs来实现，一条不在最短路上的边必定连接了两个层（连接同一层是没有意义的，不会有贡献），我们建一棵线段树，将这两个层的值更新一下 dforward[u]+w+dbackward[v] 

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG ;//cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<LL,int> P;
const int maxn = 4e5+10;
#define ls (o<<1)
#define rs (o<<1|1)
#define int long long 
LL tree[maxn<<2];
void modify(int x,int l,int r,int ql,int qr,long long v){
	if(l >= ql&&r <= qr){
		tree[x] = min(tree[x],v);
		return;
	}
	int mid = (l+r)>>1;
	if(ql <= mid)
		modify(x<<1,l,mid,ql,qr,v);
	if(qr > mid)
		modify(x<<1|1,mid+1,r,ql,qr,v);

}
long long query(int x,int l,int r,int p){
	if(l == r) return tree[x];
	int mid = (l+r)>>1;
	if(p <= mid)
		return min(tree[x],query(x<<1,l,mid,p));
	else
		return min(tree[x],query(x<<1|1,mid+1,r,p));
}
struct Edge{
	int from,to;LL w;
};
vector<Edge> edges;
vector<int> G[maxn];
void AddEdge(int u,int v,LL  w){
	edges.push_back(Edge{u,v,w});
	edges.push_back(Edge{v,u,w});
	int m = edges.size();
	G[u].Pb(m-2);
	G[v].Pb(m-1);
}
LL disf[maxn],disb[maxn],dis[maxn];
bool done[maxn];
int  p[maxn];
void Dij(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(done,0,sizeof(done));
	memset(p,-1,sizeof(p));
	dis[s] = 0;
	priority_queue<P> Q;
	Q.push(P(dis[s],s));
	while(!Q.empty()){
		int u = Q.top().second;Q.pop();
		if(done[u]) continue;
		done[u] = true;
		for(auto id: G[u]){
			int to = edges[id].to,w = edges[id].w;
			if(done[to]) continue;
			if(dis[to] > dis[u]+w){
				dis[to] = dis[u]+w;
				p[to] = id;
				// cout<<to<<" "<<p[to]<<endl;
				Q.push(P(-dis[to],to));
			}
		}
	}
}

int path[maxn],id[maxn];
bool mainpath[maxn];
vector<int> E[maxn];// 抽出来的最短路树图
void dfs(int u){
	for(auto v:E[u]){
		if(!id[v])
			id[v] = id[u];
		dfs(v);
	}
}

int32_t main(void){
	IOS;
	// cout<<(0x3f)<<endl;
	memset(tree,0x3f,sizeof(tree));
	int n,m,q;
	cin>>n>>m>>q;
	for(int i = 0;i < m; ++i){
		LL u,v,w;
		cin>>u>>v>>w;
		AddEdge(u,v,w);
	}
	// 两次dij最短路

	Dij(n);memcpy(disb,dis,sizeof(dis));
	Dij(1);memcpy(disf,dis,sizeof(dis));
	// DEBUG;
	// for(int i= 1;i <= n; ++i)
	// {
	// cout<<i<<" "<<disf[i]<<" "<<disb[i]<<endl;
	// }
	// DEBUG;
	// cout<<p[4]<<endl;
	int len = 0;
	// int i
	for(int i = n;i >= 1; ){
		path[++len] = i;
		if(i == 1) break;
		// cout<<p[i]<<endl;
		assert(p[i] != -1);
		mainpath[p[i]>>1] = true;
		i = edges[p[i]].from;
	}
	// assert()
	reverse(path+1,path+len+1);
	// cout<<len<<endl;
	for(int i = 1;i <= len; ++i)
		id[path[i]] = i;
	for(int i = 2;i <= n; ++i){
		if(p[i]>=0){
			int u = edges[p[i]].from;
			assert(edges[p[i]].to = i);
			E[u].Pb(i);
		}
	}
	dfs(1);
	// if(n == 420 )
	// {
	// cout<<len<<endl;
	// // assert(1==0);
	// }
	// for(int i = 1;i <= n; ++i)
	// cout<<i<<" "<<id[i]<<endl;
	for(int i = 0;i < edges.size(); i ++){
		if(mainpath[i>>1]) continue;
		int u = edges[i].from;
		int v = edges[i].to;
		LL w = edges[i].w;
		if(id[u] >= id[v])
			continue;
		// DEBUG;
		// cout<<u<<" "<<v<<" "<<disf[u]+disb[v]+w<<endl;
		modify(1,1,len,id[u],id[v]-1,disf[u]+disb[v]+w);
	}
	

	// cout<<"QUery"<<endl;
	int e;LL noww;
	for(int i = 1;i <= q; ++i){
		cin>>e>>noww;e--;
		LL ans = INFF;
		// assert(2*e < edges.size());
		int u = edges[2*e].from,v = edges[2*e].to,w = edges[2*e].w;
		if(id[u] > id[v])
			swap(u,v);
		// cout<<w<<endl;
		// if(i == 84)
		// cout<<mainpath[e]<<endl;
		if(mainpath[e]){
			// cout<<dis[n]-w+noww<<" "<<query(1,1,len,id[u])<<endl;
			ans = min(dis[n]-w+noww,query(1,1,len,id[u]));
		}
		else{
			// cout<<u<<" "<<disf[u]<<" "<<" "<<v<<" "<<disb[v]<<endl;
			ans = min(dis[n],min(disf[u]+disb[v],disf[v]+disb[u])+noww);
		}
		// printf("%lld\n",ans);
		cout<<ans<<endl;
	}
	







	return 0;
}
全部评论

相关推荐

头像
11-25 10:35
莆田学院 产品经理
点赞 评论 收藏
分享
11-22 18:35
南京审计大学金审学院 审计
辞退了很喜欢的实习生，总结他3个“雷点”
实习生的“雷区”：那些你需要避开的坑最近我不得不辞退了一位实习生，虽然他很努力，也很会说话，但有些行为实在让人无法忍受。总结了他的几个“雷区”，希望大家引以为戒。1.&nbsp;上班摸鱼可以，但别太嚣张大家都知道，上班时间玩手机属于“摸鱼”，但摸鱼也要有个度。这位实习生的工位就在我旁边，背后是老板。他居然敢翘着二郎腿，懒洋洋地靠在椅背上，手机举到肩膀高度，玩得不亦乐乎。你说，这是不是有点太嚣张了？摸鱼可以，但别让领导和老板看得一清二楚啊！2.&nbsp;犯错不可怕，但要敢于承认工作中犯错是难免的，关键是要及时补救和复盘，避免再犯。这位实习生经常算错数据，商品价格也会搞错，交代的工作没有后续进展。更让人无语的是，他...
点赞 评论 收藏
分享
10-23 12:06
安庆职业技术学院 后期制作
我这个能找到工作吗😭
已老实求offer😫：有点像徐坤(没有冒犯的意思哈)
点赞 评论 收藏
分享
10-09 00:50
已编辑
长江大学 算法工程师
全村唯一的指望了，怎么就偏偏是你。
成也华子，败也华子，如今竟然只能指望着华子了，害。投的是计算产品线，因为研究方向是ai-infra，只有这个最对口了。因为祖上传下来的xcpc金所以免机考+一次面试，实际在南研所只面了两轮。---------分割线---------但是我不想去，因为逆反。华子是家里唯一承认的私企。去这里等价于又一次屈服于他们。（想啥呢，人家还没给你发offer呢）
不期而遇的夏天：1.同学你面试评价不错，概率很大，请耐心等待；2.你的排名比较靠前，不要担心，耐心等待；3.问题不大，正在审批，不要着急签其他公司，等等我们！4.预计9月中下旬，安心过节；5.下周会有结果，请耐心等待下；6.可能国庆节前后，一有结果我马上通知你；7.预计10月中旬，再坚持一下；8.正在走流程，就这两天了；9.同学，结果我也不知道，你如果查到了也告诉我一声；10.同学你出线不明朗，建议签其他公司保底！11.同学你找了哪些公司，我也在找工作。
点赞 评论 收藏
分享
11-26 13:37
已编辑
贵阳人文科技学院 Web前端
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
231362次浏览 2026人参与
# 哪些公司校招卡第一学历 #
32480次浏览 102人参与
# 北方华创开奖 #
65675次浏览 545人参与
# 25届秋招总结 #
392175次浏览 3924人参与
# 在职场上，你最讨厌什么样的同事 #
5533次浏览 80人参与
# 地方国企笔面经互助 #
6413次浏览 16人参与
# 阿里云管培生offer #
57611次浏览 1739人参与
# ai智能作图 #
19342次浏览 240人参与
# 硬件兄弟们 甩出你的华为奖状 #
77726次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2434122次浏览 34693人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4631次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722088次浏览 8548人参与
# 我的实习求职记录 #
6116910次浏览 83929人参与
# 如果再来一次，你还会选择这个工作吗？ #
108513次浏览 1088人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9722次浏览 202人参与
# 签了三方后想毁约怎么办 #
18441次浏览 111人参与
# 游戏求职进展汇总 #
52508次浏览 343人参与
# 夸夸我的求职搭子 #
131889次浏览 1360人参与
# 腾讯求职进展汇总 #
207135次浏览 1693人参与
# 25届机械人为了秋招做了哪些准备？ #
24809次浏览 352人参与
# 实习想申请秋招offer，能不能argue薪资 #
35670次浏览 308人参与
# 机械求职避坑tips #
21964次浏览 237人参与
牛客网
牛客企业服务