codeforces round 686解题报告

2024-04-07 10:15:50

a.输出一个数组它的a[i] != i,有两种思路，逆序输出然后交换中间位置，另一种是直接输出i = i%n + 1

#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 1e5 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const int mod = 998244353;
ll fast_pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1)ans = (ans * a)%mod;
		a = (a * a)%mod;
		b>>=1;
	}
	return (ans%mod);
}
inline int read()
{
	int x = 0, flag = 1;
	char c = getchar();
	while(c < '0' && c > '9') {if(c == '-') flag = -1, c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0', c = getchar();}
	return x * flag;
}
typedef pair<int,int> pii;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#if DBG
	freopen("input.txt","r",stdin);
#endif
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		if(n % 2 == 0){
			for(int i = n;i >= 1;i--)
				cout<<i<<" ";
			cout<<endl;
		}else{
			for(int i = n;i >= 1;i--)
				if(i == n)
					cout<<(n  + 1)/2<<" ";
				else if(i == (n + 1)/2)
					cout<<n<<" ";
				else cout<<i<<" ";
			cout<<endl;
		}
	}
	return 0;
}

b.计数

#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 2e5 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const int mod = 998244353;
ll fast_pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1)ans = (ans * a)%mod;
		a = (a * a)%mod;
		b>>=1;
	}
	return (ans%mod);
}
inline int read()
{
	int x = 0, flag = 1;
	char c = getchar();
	while(c < '0' && c > '9') {if(c == '-') flag = -1, c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0', c = getchar();}
	return x * flag;
}
typedef pair<int,int> pii;
int cnt[N],chose[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#if DBG
	freopen("input.txt","r",stdin);
#endif
	int t ;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i = 1;i <= n;i++){
			cnt[i] = chose[i] = 0;
		}
		for(int i = 1;i<=  n;i++){
			int x;
			cin>>x;
			cnt[x]++;
			chose[x] = i;
		}
		bool f = false;
		for(int i = 1;i <= n;i++)
			if(cnt[i] == 1){
				f =true;
				cout<<chose[i]<<endl; 
				break;
			}
		if(!f)cout<<-1<<endl;
				
	}
	return 0;
}

#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 2e5 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const int mod = 998244353;
ll fast_pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1)ans = (ans * a)%mod;
		a = (a * a)%mod;
		b>>=1;
	}
	return (ans%mod);
}
inline int read()
{
	int x = 0, flag = 1;
	char c = getchar();
	while(c < '0' && c > '9') {if(c == '-') flag = -1, c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0', c = getchar();}
	return x * flag;
}
typedef pair<int,int> pii;
int a[N],cnt[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#if DBG
	freopen("input.txt","r",stdin);
#endif
	int t ;	
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i = 0;i <= n;i++)cnt[i] = 0;
		int ans = INF;
		for(int i = 1;i <= n;i++){
			cin>>a[i];
			if( a[i ] != a[i - 1])cnt[a[i]]++;
		}
		cnt[a[1]] --;
		cnt[a[n]] --;
		
		for(int i = 1;i <= n;i++){

			ans = min(cnt[a[i]] + 1,ans);
		}
		cout<<ans<<endl;
	}
	return 0;
}
turn 0;
}

d.素数分解

#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 2e5 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const int mod = 998244353;
ll fast_pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1)ans = (ans * a)%mod;
		a = (a * a)%mod;
		b>>=1;
	}
	return (ans%mod);
}
inline int read()
{
	int x = 0, flag = 1;
	char c = getchar();
	while(c < '0' && c > '9') {if(c == '-') flag = -1, c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0', c = getchar();}
	return x * flag;
}
typedef pair<int,int> pii;
int prime[N];
vector<int> p;
void get(){
	for(int i = 2;i < N;i++){
		if(!prime[i]){
			p.pb(i);
			for(int j = i;j < N;j += i)prime[j] = 1;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#if DBG
	freopen("input.txt","r",stdin);
#endif
	get();
	//cout<<p.size()<<endl;
	int t;
	cin>>t;
	vector<int> cnt(p.size());
	while(t--){
		ll n;
		cin>>n;
		for(int i = 0;i < p.size();i++){
			cnt[i] = 0;
		}
		int maxn = 1,idx = 0;
		ll nn = n;
		for(int i = 0;i < p.size();i++){
			while(nn%p[i] == 0){
				nn/=p[i];
				cnt[i] ++;
			}
			if(cnt[i] > maxn){
				maxn = cnt[i];
				idx  = i;
			}
		}
		cout<<maxn<<endl;
		if(maxn > 1){
			for(int i = 1;i < maxn;i++){
				cout<<p[idx]<<" ";
				n/=p[idx];
			}
			cout<<n<<endl;
		}else cout<<n<<endl;
	}
	return 0;
}

e.类似拓扑排序删边

#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 2e5 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const int mod = 998244353;
ll fast_pow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1)ans = (ans * a)%mod;
		a = (a * a)%mod;
		b>>=1;
	}
	return (ans%mod);
}
inline int read()
{
	int x = 0, flag = 1;
	char c = getchar();
	while(c < '0' && c > '9') {if(c == '-') flag = -1, c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0', c = getchar();}
	return x * flag;
}
typedef pair<int,int> pii;
vector<int> g[N];
int in[N];
struct Union_Find{
	int d[N],num[N];
	void init(int n){
		for(int i = 0; i < n;i++){
			d[i] = i;
			num[i] = 1;
		}
	}	
	int find(int x){
		return x == d[x]?x:d[x] = find(d[x]);
	}
	bool is_root(int x){
		return x == d[x];
	}
	bool merge(int x,int y){
		x = find(x);
		y = find(y);
		if(x == y)return false;
		if(num[x] > num[y])swap(x,y);
		d[x] = y;
		num[y] += num[x]; 
	}
}U; 
void solve(){
	int n;
	cin>>n;
	for(int i = 1;i <= n;i++){
		g[i].clear();
		in[i] = 0;
	}
	for(int i = 1;i <= n;i++){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
		in[u]++;
		in[v]++;
	}
	queue<int> q;
	for(int i = 1;i <= n;i++){
		if(in[i] == 1)q.push(i);
	}
	U.init(n + 1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int v : g[u]){
			in[v]--;
			U.merge(u,v);
			if(in[v] == 1)q.push(v);
		}
	}
	ll ans = n * (n - 1LL);
	for(int i = 1;i <= n;i++)
		if(U.is_root(i))
			ans -= U.num[i] * (U.num[i] - 1LL) / 2;
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#if DBG
	freopen("input.txt","r",stdin);
#endif
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

f.线段树 + 二分

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;

struct Segment_tree{
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define debug(x) cout<<#x<<" is "<<(x)<<endl
	const  static int maxn = 2e5  + 5;
	int n;
	ll a[maxn];
	ll tree_min[maxn<<2],tree_max[maxn<<2];
	ll lazy_tag[maxn<<2];
	void init(int n){
		this->n = n;
		for(int i = 1;i <= n;i++)a[i] = 0;
		for(int i = 1;i <= (n<<2) + 5;i++)
			tree_min[i] = tree_max[i] = lazy_tag[i] = 0; 
	}
	void read(){
		for(int i = 1;i <= n;i++)
			cin>>a[i];
	}
	void up(int x){
		tree_min[x] = min(tree_min[lc(x)],tree_min[rc(x)]);
		tree_max[x] = max(tree_max[lc(x)],tree_max[rc(x)]);
	}
	void build(int x,int l,int r){
		if(l == r){
			tree_min[x] = a[l];
			tree_max[x] = a[l];
			return;
		}
		int mid = (l + r)>>1;
		build(lc(x),l,mid);
		build(rc(x),mid + 1,r);
		up(x);
	}
	ll query_min(int x,int l,int r,int ql,int qr){
		if(l >= ql && r <= qr){
			return tree_min[x];
		}
		ll ans = INF;
		int mid = (l + r)>>1;
		if(ql <= mid)
			ans = min(ans,query_min(lc(x),l,mid,ql,qr));
		if(qr > mid)
			ans = min(ans,query_min(rc(x),mid + 1,r,ql,qr));
		return ans; 
	}
	ll query_max(int x,int l,int r,int ql,int qr){
		if(l >= ql && r <= qr){
			return tree_max[x];
		}
		ll ans = -INF;
		int mid = (l + r)>>1;
		if(ql <= mid)
			ans = max(ans,query_max(lc(x),l,mid,ql,qr));
		if(qr > mid)
			ans = max(ans,query_max(rc(x),mid + 1,r,ql,qr));
		return ans; 
	}
}seg;
void solve(){
	int n;
	cin>>n;
	seg.init(n);
	seg.read();
	seg.build(1,1,n);
	for(int x = 1;x <= n - 2;x++){
		ll seg1 = seg.query_max(1,1,n,1,x);
		int l = x + 1, r = n - 1;
		while(l <= r){
			int y = (l + r)>>1;
			ll seg2 = seg.query_min(1,1,n,x + 1,y);
			ll seg3 = seg.query_max(1,1,n,y + 1,n);
			int yy = y - x;
			int zz = n - x - yy;
			if(seg2 > seg1 || seg3 > seg1){
				l = y + 1;
			}else if(seg2 < seg1 || seg3 < seg1){
				r = y - 1;
			}else{
				puts("YES");
				y = y - x;
				int z = n - x - y;
				cout<<x<<" "<<y<<" "<<z<<endl; 
				return;
			}
		}
		
	}
	puts("NO");
}
void fastIO(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
int main(){
	//fastIO();
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

码农公寓

相关文章