备孕百度之星-9月22日

随机题意

#include <bits/stdc++.h>
using namespace std;
int a[100005];
//随机题意 
int main()
{
	int T;
	int n, k;
	cin >> T;
	while(T-- > 0){
		cin >> n >> k;
		for(int i = 0; i < n; i++) cin >> a[i];
		sort(a, a + n);
		int cur = a[0] - k;
		int res = 0;
		for(int i = 0; i < n; i++){
			int l = a[i] - k, r = a[i] + k;
			if(cur > r) continue;
			if(l <= cur && cur <= r){
				cur++;
				res++;
			}else{
				cur = l+1;
				res++;
			}
		}
		cout << res << endl;
	}
}

魔怔

#include <bits/stdc++.h>
using namespace std;
string a[1005];
int d[1005];
int o[1005];
int fa[1005];

int Find(int x){
	if(fa[x] == x) return x;
	return fa[x] = Find(fa[x]);
}

int main()
{
	int T;
	int n, s;
	cin >> T;
	while(T-- > 0){
		cin >> n >> s;
		s -= 1;
		for(int i = 1; i < n; i++) cin >> a[i];
		memset(o, 0, sizeof(o));
		int sum = 0;
		
		for(int i = 0; i < n; i++) fa[i] = i;
		for(int i = 1; i < n; i++){
			for(int j = 0; j < i; j++){
				if(a[i][j] == '0'){
					if(Find(i) != Find(j)) fa[Find(i)] = Find(j);
					o[i]++;
					o[j]++;
					sum++;//共多少0 
				}
			}
		}
		int ji = 0;
		for(int i = 0; i < n; i++) if(o[i] % 2 == 1) ji++;
		if(ji > 2) {
			cout << -1 << endl;
			continue;
		}
		if((ji == 2) && (o[s] % 2 == 0)){
			cout << -1 << endl;
			continue;
		}
		int ans = 0;
        //一开始在不在白色上
        if(o[s] == 0) ans++;
        //找联通分量
		for(int i = 0; i < n; i++){
			if(o[Find(i)] != 0){
				ans++;
				o[Find(i)] = 0;
			}
		}
		int res = (ans-1) * 2 + sum;
		cout << res << endl;
	}
}

考虑出了并查集的做法。但忽略了起始点在黑色节点可行解的情况，找了很久才发现这个bug。所以一开始就要分析的很透彻，不然编码后很难在找到思路上错误的bug。

hduoj被卡常，用o3优化： #pragma GCC optimize(3,"Ofast","inline")

补一个欧拉回路的dfs模板（poj2230）

//#include <bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
#include<vector>
#include <algorithm>

using namespace std;
//vector建图 
vector<int> g[10001];

void dfs(int x){
	while(!g[x].empty()){
		int j = g[x][g[x].size()-1];
		g[x].pop_back();
		dfs(j);
	}
	cout << x << endl;
} 

int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) g[i].clear();
	while(m--){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(1);
	return 0;
}

净化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
int n;
ll m;

// 快读
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 

ll llread(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
void slove(){
	//只有前两轮操作特殊，之后不存在净化操作
	ll x = 0;
	for(int i = 0; i < n; i++){
		x += a[i];
		if(x < 0) x = 0;
		if(x >= m) {
			cout << 1 << endl;
			return ;
		}
	}
	if(x == 0) {
		cout << -1 << endl;
		return ;
	}
	ll t1 = x;
	ll ma = 0;
	for(int i = 0; i < n; i++){
		x += a[i];
		if(x < 0) x = 0;
		if(x >= m) {
			cout << 2 << endl;
			return ;
		}
		ma = max(ma, x);
	}
	ll t2 = x;
	if(t1 == t2){
		cout << -1 << endl;
		return ;
	}
	ll sub = t2-t1;
	ll zmax = ma - t1;
	ll res = 3 + (m - zmax - t2 + sub - 1) / sub;
	cout << res << endl;
}

int main()
{
	int T;
	read(T);
	while(T-- > 0){
		read(n);
		llread(m);
		for(int i = 0; i < n; i++) llread(a[i]);
		slove();
	}
}

水题

//#include <bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
#include<vector>
#include <algorithm>
typedef long long ll;
using namespace std;

// 快读
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 

ll llread(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
int a[100005];
int main()
{
	int T ;
	read(T);
	while(T-- > 0){
		int n;
        read(n);
		int cnt = 0;
		for(int i = 1; i <= n; i++) read(a[i]);
		for(int i = 1; i <= n; i++) if(a[i] == i) cnt++;
		if(cnt > 100){
			cout << "First" << endl;
		}else{
			cout << "Second" << endl;
		}
	}
}

看不懂这题

环上游走

#include<iostream>
#include<cstring>
using namespace std;
int res;
int n;
int v[85];

void dfs(int x, int cur){
	if(cur == n){
		res++;
		return ;
	}
	int p = x-cur;
	if(p <= 0) p += n; 
	if(!v[p]){
		v[p] = 1;
		dfs(p,cur+1);
		v[p] = 0;
	}
	p = x+cur;
	if(p > n) p -= n;
	if(!v[p]){
		v[p] = 1;
		dfs(p,cur+1);
		v[p] = 0;
	}
}

int main(){
	int T;
	cin >> T;
	while(T-- > 0){
		cin >> n;
		res = 0;
		memset(v, 0, sizeof(v));
		v[1] = 1;
		dfs(1,1);
		cout << res << endl;
	}
}