小白月赛题

小白月赛30

A-黑白边：并查集

思路：
1）先把所有黑白连起来，用并查集来维护连通块
2）然后看白边的两个点是否在一个联通块内，如果不在则连起来，白边个数+1
3）最后如何来判断所有点是否联通呢？只需要判断f[i] == i是否成立，是一个联通快的话，只有一个点的f[i]=i，其余的都不会，如果有多个，说明有多个连通块，也就是所有点不连通。这也是判断连通块个数的好方法。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

struct Edge{
	int u,v;
}edge[500005];

int head[200005],cnt = 0,f[200005],n,m;
int find(int x)
{
	if(x != f[x]) return f[x] = find(f[x]);
    return f[x];
}

void merge(int x,int y)
{
	x = find(x);
	y = find(y);
	if(x != y) f[x] = f[y];
}

int main()
{
	ios::sync_with_stdio(false);
	int x,y,w,t = 0;
	scanf("%d%d",&n,&m);
	//init();
	for(int i = 0; i <= n; i++) f[i] = i;
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d",&x,&y,&w);
		if(w == 0){
		    //add(x,y,w);
	    	//add(y,x,w);
	    	merge(x,y);
		}
		else{
			edge[t].u = x;
			edge[t++].v = y; 
		}
	}
	int cnt = 0,flag = 0;
	for(int i = 0; i < t; i++){
		if(find(edge[i].u) != find(edge[i].v)){
			merge(edge[i].u,edge[i].v);
			cnt++;
		}
	}
	int num = 0;
	for(int i = 1; i <= n; i++){
		if(f[i] == i){
			num++;
		}
		if(num >= 2) break;
	}
	if(num >= 2) printf("-1");
	else printf("%d",cnt);
    return 0;	
}

B-最好的宝石：线段树

思路：线段树单点修改和区间查询，在查询最大值的过程中顺便计算最大值个数。
计算方法：如果左边和右边最大值相等，那么最大值个数为左右相加，如果小于右边，那么最大值个数等于右边最大值个数，反之等于左边最大值个数。 
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

ll tree[1000005],tree1[1000005];
int n,m,x,y;
ll w[200005];
void pushdown(int xb)
{
	if(tree[xb*2] == tree[xb*2+1]){
		tree[xb] = tree[xb*2];
		tree1[xb] = tree1[xb*2]+tree1[xb*2+1];
	}
	else if(tree[xb*2] > tree[xb*2+1]){
		tree[xb] = tree[xb*2];
		tree1[xb] = tree1[xb*2];
	}
	else{
		tree[xb] = tree[xb*2+1];
		tree1[xb] = tree1[xb*2+1];
	}
}

void build(int xb,int l,int r)
{
	if(l == r){
		tree[xb] = w[l];
		tree1[xb] = 1;
		return;
	}
	int mid = (l+r) >> 1;
	build(xb*2,l,mid);
	build(xb*2+1,mid+1,r);
	pushdown(xb);
}

void update(int xb,int l,int r,int X,int Y)
{
	if(l == r){
		w[X] = Y;
		tree[xb] = Y;
		tree1[xb] = 1;
		return;
	}
	int mid = (l+r) >> 1;
	if(X <= mid) update(xb*2,l,mid,X,Y);
	else update(xb*2+1,mid+1,r,X,Y);
	pushdown(xb);
}

ll num = 0;
pair<ll,ll> ask(int xb,int l,int r,int L,int R)
{
	if(L <= l && R >= r){
		return {tree[xb],tree1[xb]};
	}
	int mid = (l+r) >> 1;
	if(R <= mid) return ask(xb*2,l,mid,L,R);
	else if(L > mid) return ask(xb*2+1,mid+1,r,L,R);
	else{
		auto t1 = ask(xb*2,l,mid,L,R);
		auto t2 = ask(xb*2+1,mid+1,r,L,R);
		if(t1.first == t2.first) {
			return {t1.first,t1.second+t2.second};
		}
	    else if(t1.first > t2.first) return t1;
    	else return t2;
	}
	
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++) scanf("%lld",&w[i]);
	build(1,1,n);
	while(m--){
		char s[55];
		scanf("%s",s);
		if(strcmp("Change",s) == 0){
			scanf("%d%d",&x,&y);
			update(1,1,n,x,y);
//			for(int i = 1; i <= 2*n+1; i++) printf("%d ",tree[i]);
//			cout << "\n";
		}
		else{
			num = 0;
			scanf("%d%d",&x,&y);
			auto ans = ask(1,1,n,x,y);
			printf("%lld %lld\n",ans.first,ans.second);
		}
	}
    return 0;	
}

C-滑板上楼梯

超时代码： 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int main()
{
	ll n,ans=0;
	cin >> n;
	int xx = 0;
	while(n){
		if((n&1) && (n>>1) >= 0 && ((n>>1)&1) && !xx){
			n -= 3;
			xx = 1;
			ans++;
		}
		else{
			ans++;
			n -= 1;
			xx = 0;
		}
	}
	cout << ans;
    return 0;	
}

正解： 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int main()
{
	ll n,ans=0;
	cin >> n;
	ll xx = 0;
	ll cnt = n/3;
	ll ys = n%3;
	ll nd = cnt-1;
	if(n == 0) cout << 0;
	else{
		if(nd <= ys){
			cout << cnt+ys;
		}
		else{
			ll t;
			if((nd-ys)%4){
				t = (nd-ys)/4+1;
			}
			else t = (nd-ys)/4;
			ans = cnt-t+t*3+ys;
			cout << ans;
		}
	}
    return 0;	
}

H-第k小：大根堆与小根堆的运用

思路：大根堆在下，小根堆在上，并且保证大根堆的大小是小于等于k的。 


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

priority_queue<int>q1;//大 
priority_queue<int,vector<int>,greater<int> >q2;//小
int a[200005]; 
int main()
{
	int n,m,k,x,d;
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i = 1; i <= n; i++){
		if(q1.size() < k){
			q1.push(a[i]);
		}
		else q2.push(a[i]);
	}
	for(int i = 1; i <= m; i++){
		scanf("%d",&d);
		if(d == 1){
			scanf("%d",&x);
			if(q1.size() < k){
				q1.push(x);
				continue;
			}
			if(x <= q1.top()){
				if(q1.size() >= k){
					int t = q1.top();
			    	q2.push(t);
			    	q1.pop(); 
			    	q1.push(x);
				}
				else{
					q1.push(x);
				}
			}	
			else {
				q2.push(x);
			}
		}
		else{
			if(q1.size() < k) cout << -1 << endl;
			else cout << q1.top() << endl;
		}
	}
    return 0;	
}

J-小游戏：dp

思路：
dp三步走
1）找状态：dp[i][1] 表示选i这个数的最大分数，dp[i][0]表示不选i的最大分数
2）状态转移: dp[i][0] = max(dp[i-1][1],dp[i-1][0]) 不选i， 选i,那么i-1不能选 dp[i][1] = dp[i-1][0] + num[i]*i
3）赋初值： 这题不用
存在一个问题，选i不是i-1和i+1都不能选吗，为什么只考虑i-1，不考虑i+1呢？
很简单，因为i后面的数考虑了选不选i-1，这不就是相当于在选i-2的时候i-1就不能选考虑进去了吗，所有在选的时候不必考虑后面的，因为在选后面的时候相当于会将这个考虑进去。 


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int a[200005];
int num[200005];
ll dp[200005][2];
int main()
{
	int n;
	cin >> n;
	int mmax = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		num[a[i]]++;
		mmax = max(mmax,a[i]);
	}
	for(int i = 1; i <= mmax; i++){
		dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
		dp[i][1] = dp[i-1][0]+num[i]*i;
	} 
	cout << max(dp[mmax][1],dp[mmax][0]);
    return 0;	
}



小白月赛29

B-二进制：位运算

思路：对于每个数对应的每一个二进制位，要么是1，要么是0，所有先设x=0，y=1，int整形范围内每个数最多有20位，然后我们计算每一位经过所有操作最后会得到什么。
如果x=0&&y=0，那么对于所有数经过这些操作，其实就是这位&0就够了
如果x=1&&y=0，数翻转，这位&1
如果x=0&&y=1，&1 |1 ^1 都可以，那就不进行操作
如果x=1&&y=1，这位 |1
对于与上的数，我们最开始将它所有位先置位1，因为之后要改也是变为0，同样的^ | 最先置为0。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int opt[500005],a[500005];
int main()
{
	int n;
	cin >> n;
	int x = 0,y = 1;
	int an = (1 << 20)-1,r=0,l=0;
	for(int i = 1; i <= n; i++){
		cin >> opt[i] >> a[i];
	}
	for(int i = 0; i < 20; i++){
		x = 0,y = 1;
		for(int j = 1; j <= n; j++){
			int w = (a[j] >> i) & 1;
			if(opt[j] == 1){
				x &= w;
				y &= w;
			}
			else if(opt[j] == 2){
				x |= w;
				y |= w;
			}
			else{
				x ^= w;
				y ^= w;
			}	
		}
		if(x == 0 && y == 0){
			an ^= (1 << i);
		}
		else if(x == 1 && y == 0){
			r ^= (1 << i);
		}
		else if(x == 1 && y == 1){
			l ^= (1 << i);
		}
	}
	cout << 3 << endl;
	cout << 1 << " " << an << endl;
	cout << 2 << " " << l << endl;
	cout << 3 << " " << r << endl;
    return 0;	
} 

D-种树：贪心+树形dp

思路：设用大剪刀的次数为m，对于层数小于m的可以剪的节点我们考虑去用大剪刀，其它的用小剪刀。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 998244353 ;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;
  
using namespace std;

vector<int>a[800005];
ll v[500005];
int n,l,r,m = 0;

ll dfs(int s,int fa,int h)
{
	int len = a[s].size();
	if(!len){
		return v[s];
	}
	if(h <= m){
		ll t1 = dfs(a[s][0],s,h+1);
		ll t2 = dfs(a[s][1],s,h+1);
		return max(t1,t2);
	}
	else{
		ll t1 = dfs(a[s][0],s,h+1);
		ll t2 = dfs(a[s][1],s,h+1);
		return min(t1,t2);
	}
}

int main()
{
	
	cin >> n;
	for(int i  = 1; i <= n; i++){
		cin >> l >> r;
		if(l != 0 && r != 0){
			m++;
			a[i].push_back(l);
			a[i].push_back(r);
		}
	}
	m = (m+1)/2;
	for(int i = 1; i<= n; i++) cin >> v[i];
	cout << dfs(1,0,1);
	return 0;
}

F-项链：链表操作

提示：
对于数d，d=0或1
x = 1^d
y = d
x一定不等于y 


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 20000311;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int f[2][100005];
int main()
{
	int n,m,opt,x,y,d=0;
	cin >> n >> m;
	f[1][1] = 2;
    f[0][1] = n;
	f[0][n] = n-1;
	f[1][n] = 1;
	for(int i = 2; i < n; i++) f[0][i] = i-1,f[1][i] = i+1;
	for(int i = 1; i <= m; i++){
		cin >> opt;
		if(opt == 1){
			cin >> x >> y;
			f[1^d][f[d][x]] = f[1^d][x];
			f[d][f[1^d][x]] = f[d][x];
			
			f[1^d][x] = f[1^d][y];
			f[d][f[1^d][y]] = x;
			
			f[1^d][y] = x;
			f[d][x] = y;
		}
		if(opt == 2){
			cin >> x >> y;
			f[1^d][f[d][x]] = f[1^d][x];
			f[d][f[1^d][x]] = f[d][x];
			
			f[d][x] = f[d][y];
			f[1^d][f[d][y]] = x;
			
			f[d][y] = x;
			f[1^d][x] = y;
		}
		if(opt == 3) d ^= 1;
		if(opt == 4){
			cout << 1 << " ";
			for(int i = f[1^d][1]; i != 1; i = f[1^d][i]){
				cout << i << " ";
			}
			cout << endl;
		}
	}
	return 0;
}



小白月赛28

C-单词记忆方法 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

string s;
stack<int>st1;
int main()
{
	cin >> s;
	int l = s.size();
	for(int i = 0; i < l; i++){
		if(s[i] == '('){
			st1.push(0);
		}
		else if(s[i] == ')'){
			int res = 0;
			while(s[i+1] >= '0' && s[i+1] <= '9'){
				res = res*10 + s[i+1] - '0';
				i++;
			}
			if(res == 0) res = 1;
			int t = st1.top();
			st1.pop();
			res *= t;
			t = 0;
			if(st1.size()){
		    	t = st1.top();
		    	st1.pop(); 
	    	}
			st1.push(t+res);
		}
		else if(s[i] >= 'A' && s[i] <= 'Z'){
			int res = 0;
			int k = s[i] - 'A' + 1;
			while(s[i+1] >= '0' && s[i+1] <= '9'){
				res = res*10 + s[i+1] - '0';
				i++;
			}
			if(res == 0) res = 1;
			res = res * k;
			t = 0;
			if(st1.size()){
		    	int t = st1.top();
		    	st1.pop();
		    }
			st1.push(res+t);
		}
	}
	int ans = 0;
	cout << st1.top() << endl;
	return 0;
}

D-位运算之谜 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

ll a[200005],sum[200005];
int main()
{
	ll t,x,y;
	cin >> t;
	while(t--){
    	cin >> x >> y;
    	x = x - 2*y;
	    if(x < 0 || (x&y)) {
	    	cout << "-1" << endl;
	    	continue;
		}
		cout << x << endl;
	}
	return 0;
}

G-牛牛和字符串的日常：KMP

思路：利用kmp去匹配模式串中能匹配到的最大长度。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

char s[100005],t[100005];
int nxt[100005];
void getNext()
{
	int i,j,l;
	l = strlen(s);
	i = 0,j = -1;
	nxt[0] = -1;
	while(i < l && j < l){
		if(j == -1 || s[i] == s[j]){
			i++;
			j++;
			nxt[i] = j;
		}
		else{
			j = nxt[j];
		}
	}
}

int kmp()
{
	int i,j,l1,l2,ans = 0;
	l1 = strlen(t);
	l2 = strlen(s); 
	i = 0,j = 0;
	while(i < l1 && j < l2){
		if(j == -1 || t[i] == s[j]){
			i++;
			j++;
		}
		else{
			ans = max(ans,j);
			j = nxt[j];
		}
		if(j == l2) return l2;
		if(i == l1) ans = max(ans,j);
	}
	return ans;
}

int main()
{
	int n;
	scanf("%s",s);
	scanf("%d",&n);
	getchar();
	getNext();
//	for(int i = 0; i < 7; i++) cout << next[i] << endl;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		scanf("%s",t);
		cnt += kmp();
	//	cout << kmp() << endl;
	}
	printf("%d\n",cnt);
	return 0;
}

H-上学要迟到了：最短路

思路：每个车站用双向边连，同一辆车能到达的车站用单边连，用vector保存辆车能到达的车站，并且车站时从左往右依次连接的。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

struct edge{
	int v,val,next;
}edge[40000005];

struct node{
	int x,d;
	node(int a,int b){
		x = a;
		d = b;
	}
	bool operator < (const node& a)const{
		return d > a.d;
	}
};

int Time[1000005],head[1000005],d[1000005],vis[1000005];
int n,m,s,t,T,cnt = 0;
vector<int>a[1000005];
void add(int u,int v,int val)
{
    edge[cnt].v = v;
    edge[cnt].val = val;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void init()
{
	for(int i = 0; i <= n; i++) head[i] = -1;
}

void dijkstra()
{
	for(int i = 0; i <= n; i++) d[i] = 1e9+7,vis[i] = 0;
	priority_queue<node>q; 
	d[s] = 0;
	q.push(node(s,0));
	while(!q.empty()){
		node h = q.top();
		q.pop();
		//cout << vis[h.x] << endl;
		if(vis[h.x]) continue;
		vis[h.x] = 1;
		for(int i = head[h.x]; ~i; i = edge[i].next){
		//	cout << i << endl;
			int to = edge[i].v;
			int val = edge[i].val;
		//	cout << val << endl;
			if(vis[to]) continue;
			if(d[to] > d[h.x] + val){
				d[to] = d[h.x] + val;
				q.push(node(to,d[to]));
			}
		}
	}
}

int main()
{
	cin >> n >> m >> s >> t >> T;
	init();
	for(int i = 1; i < n; i++){
		add(i,i+1,T);
		add(i+1,i,T);
	}
	for(int i = 1; i <= m; i++){
		cin >> Time[i];
	}
	int x;
	for(int i = 1; i <= n; i++){
		cin >> x;
		a[x].push_back(i);
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j < a[i].size(); j++){
			add(a[i][j-1],a[i][j],Time[i]);
		}
	}
	dijkstra();
	cout << d[t];
	return 0;
}


J-树上行走

思路：题目所说的尽可能有更多的点可以活动，意思就是对于每个进入点，能够到达点数最多的点是哪个，可能会有多个，其实就是判断连通块的大小。而这些能够到达的他们的祖先是相同的，所有可以用并查集来做，把边相同并且两个点的类型相同的化就合并起来。那么如何判断连通块的大小呢，直接遍历每个点，查找他们的祖先，并做++操作，即sum[find[i]]++,找到最大值后，判断sum[find[i]] = 最大值的点保存起来就可以了。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

int a[200005],b[200005],sum[200005],tp[200005];
int find(int x)
{
	return x == a[x] ? a[x] : a[x] = find(a[x]);
}

void merge(int x,int y)
{
	x = find(x);
	y = find(y);
	if(x != y) a[x] = a[y];
}

int main()
{
	int n,u,v;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",&tp[i]);
		a[i] = i;
	}
	for(int i = 1; i < n; i++){
		scanf("%d%d",&u,&v);
		if(tp[u] == tp[v]){
			merge(u,v);
		}
	}
	int mmax = 0;
	for(int i = 1; i <= n; i++){
		int k = find(i);
		sum[k]++;
		mmax = max(mmax,sum[k]);
	}
	int t = 0;
	for(int i = 1; i <= n; i++){
		if(mmax == sum[find(i)]){
			b[t++] = i;
		}
	}
	sort(b,b+t);
	printf("%d\n",t);
	for(int i = 0; i < t; i++){
	    printf("%d ",b[i]);
	}
	return 0;
}

I-迷宫

思路：没想到可以直接暴力。开一个三维数组，dp[i][j][k]=true表示从其它位置到[i,j]位置存在和为k的路径，到[i,j]位置可以从[i-1,j],[i,j-1]过来，所有枚举dp[i-1][j][0-1e4+7] 和 dp[i][j-1][0-1e4+7] 为true的加上a[i][j]取模便可求得[i,j]位置权值和有哪些。
注意：dp要是bool型的，int型会超内存。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

ll a[105][105];
bool dp[105][105][10010];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d",&a[i][j]);
		}
	}
	dp[1][1][a[1][1]%mod] = true;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int k = 0; k <= 10007; k++){
				if(i == 1 && j == 1) continue;
				int x = (k+a[i][j]) % mod;
				if(dp[i-1][j][k]) dp[i][j][x] = true;
				if(dp[i][j-1][k]) dp[i][j][x] = true;
			}
		}
	}
	int cnt = 0;
	for(int i = 0; i <= 10007; i++){
		if(dp[n][m][i]) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}
bitset做法
同类题： 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

int n,m;
ll a[105][105],dp[105][105];
bool  check(ll x)
{
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = 0;
		}
	}
	if(a[1][1] + x <= 0) return false;
	dp[1][1] = x + a[1][1];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i == 1 && j == 1) continue;
			ll k1=0,k2=0;
			if(i == 1) k1 = a[i][j] + dp[i][j-1];
			else if(j == 1) k1 = a[i][j] + dp[i-1][j];
			else {
			    k1 = a[i][j] + dp[i-1][j];
			    k2 = a[i][j] + dp[i][j-1];
	    	}
			if(k1 <= 0 && k2 <= 0){
				dp[i][j] = -ds;
			}
			else {
				dp[i][j] = max(k1,k2);
			}
		}
	}
	if(dp[n][m] == -ds || dp[n][m] <= 0) return false;
	return true;
}

int main()
{
	ll ans = 0;
	ll l = 1,r = 1e14;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%lld",&a[i][j]);
		}
	}
	while(l <= r){
		ll mid = (l+r) >> 1;
		if(check(mid)){
		    ans = mid;
		    r = mid-1;
		}
		else l = mid+1;
	}
	printf("%lld",ans);
	return 0;
}

小白月赛27


A-巨木之森：贪心+树直径

思路：
1：从某个点开始遍历完所有的点，因为可能会有回退，回退部分的距离为边长度乘以2，而要根据题意要求最多的队数，那么就是走完所有点的距离最短，贪心在此，也就是说我们要尽可能让回退边减少，所有我们要找一天距离开始点最远的点，从这个点到最远点不让回退边出现，那么遍历完所有点要走的路的距离为sum*2-len[i]，sum是所有所有路径之和，i是距离开始点最远的点是哪个。从式子也可以看出要优先找len[i]最大的点。
2：那如何找呢？这里要引入树的直径的性质了，树的直径中有一条重要的性质就是，离任意点最远的是树的直径的端点的一个，所有我们只要找到这个两个端点，然后求出所有点距离最远的点的长度，排序，优先取长的即可。 


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

struct edge{
	int v,w,next;
}edge[500005];

int head[100005],vis[100005],cnt = 0,n;
ll m;
int d[2];
void add(int u,int v,int w)
{
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

void init()
{
	for(int i = 0; i <= n; i++) head[i] = -1;
}

ll max_l = 0;
ll len[100005];
void dfs(int s,int f,ll l,int t)
{
	if(t != 0){
		len[s] = max(len[s],l);//因为有两个端点，那么取其中最大的那个。
	}
	if(l > max_l && t != 2){
		max_l = l;
		d[t] = s;
	}
	for(int i = head[s]; ~i; i = edge[i].next){
		int v = edge[i].v;
		int w = edge[i].w;
		if(v == f) continue;
		dfs(v,s,l+w,t);
	}
}

bool cmp(ll x,ll y)
{
	return x > y;
}

int main()
{
	int u,v,w;
	ll sum = 0;
    scanf("%d%lld",&n,&m);
	init();
	for(int i = 1; i < n; i++){
		scanf("%d%d%d",&u,&v,&w);
		sum += w;
		add(u,v,w);
		add(v,u,w);
	}
	sum *= 2;
	dfs(1,0,0,0);//找第一个端点
	max_l = 0;
	dfs(d[0],0,0,1);//利用第一个端点找第二个端点
	dfs(d[1],0,0,2);
	sort(len+1,len+n+1,cmp);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(m >= sum-len[i]) ans++,m -= (sum-len[i]);
	//	cout << len[i] << " ";
	}
	printf("%d\n",ans);
	return 0;	
} 


H-社团游戏：前缀和+二分

思路：先用二维前缀和统计26个英文字母出现的个数，然后对于每对(i，j)二分它的长度。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e4+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

int sum[505][505][30];
char s[505][505],a[505][505];
int n,m,k;
bool check(int i,int j,int x)
{
    for(int l = 0; l < 26; l++){
    	int cnt;
    	cnt = sum[i+x-1][j+x-1][l] - (sum[i+x-1][j-1][l] + sum[i-1][j+x-1][l] - sum[i-1][j-1][l]);
    	if(cnt > k) return false;
	}	
	return true;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; i++){
		scanf("%s",s[i]+1);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			int p = s[i][j] - 'a';
			for(int l = 0; l < 26; l++){
				sum[i][j][l] = sum[i][j-1][l] + sum[i-1][j][l] - sum[i-1][j-1][l] + (p == l ? 1 : 0);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			int ans = 1,l = 1,r = min(n-i+1,m-j+1);
			while(l <= r){
				int mid = (l+r) >> 1;
				if(check(i,j,mid)){
					ans = mid;
					l = mid+1;
				}
				else r = mid-1;
			}
			printf("%d ",ans);
		}
		printf("\n");
	}
	return 0;
}

I-名作之壁：尺取法+单调队列

第一次使用数组实现单调队列^-^
思路：
1：先确定左端点l，然后对于每个右端点r，找l-r内的最大值和最小值，看二者的之是否大于k，如果大于，说明以r-n之间的数为端点的区间都符合，sum += n-r+1，这是因为r-n之间的最大值只会大于等于l-r内的最大值，最小值也是同理。
2：然后用单调队列取找l-r内的最大值和最小值。
3：双指针控制l，r。 


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

ll mmax[10000007],mmin[10000007],a[10000007];
int main()
{
	ll n,b,c;
    ll k;
	scanf("%lld%lld",&n,&k);
	scanf("%lld%lld%lld",&a[0],&b,&c);
	for(int i = 1; i <= n; i++){
		a[i] = (a[i-1]*b+c)%mod;
	}
	int l = 1,r = 1,mmax_l = 0,mmax_r = 0,mmin_l = 0,mmin_r = 0;
	ll sum = 0;
	while(r <= n){
		while(mmax_l < mmax_r && a[mmax[mmax_r-1]] <= a[r])
		    mmax_r--;
		while(mmin_l < mmin_r && a[mmin[mmin_r-1]] >= a[r])
		    mmin_r--;
		mmax[mmax_r++] = r;
		mmin[mmin_r++] = r;
		while(a[mmax[mmax_l]] - a[mmin[mmin_l]] > k){
		    sum += n-r+1,l++;
		    if(mmax[mmax_l] < l) mmax_l++;
		    if(mmin[mmin_l] < l) mmin_l++;
		} 
		r++;
	}
	printf("%lld\n",sum);
	return 0;	
} 



小白月赛24

I-求和：dfs序+树状数组 


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;


ll val[1000005],tree[1000005];
int fa[1000005],en[1000005],node[1000005],cnt = 0;
vector<int>edge[1000005];
void add(int x,int val)
{
	while(x <= cnt){
	    tree[x] += 1ll*val;
	    x += (x & (-x));
	}
}

ll sum(int x)
{
	ll ans = 0;
	while(x){
		ans += tree[x];
		x -= (x & (-x)); 
	}
	return ans;
}

void dfs(int s,int f)
{
	fa[s] = ++cnt;
	node[cnt] = val[s];
    int l = edge[s].size();
	for(int i = 0; i < l; i++){
		int v = edge[s][i];
		if(f == v) continue;
		dfs(v,s);
	}
	en[s] = cnt;//子树的最后一个节点。	
}

int main()
{
	ios::sync_with_stdio(false);
    int n,m,k,u,v;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> val[i];
    for(int i = 1; i < n; i++){
    	cin >> u >> v;
    	edge[u].push_back(v);
    	edge[v].push_back(u);
	}
	dfs(k,0);
	for(int i = 1; i <= cnt; i++){
		add(i,node[i]);
	}
	int op,a,x;
	for(int i = 1; i <= m; i++){
		cin >> op;
		if(op == 1){
			cin >> a >> x;
			add(fa[a],x);
		}
		else{
			cin >> a;
			cout << sum(en[a]) - sum(fa[a] - 1) << endl;
		}
	}
	return 0;
}

小白月赛23

A-膜法记录 O(n*m*2^20)


思路：因为行数比较少，那么可以二进制枚举行，然后再看列的情况，如果某个点为*，但是它所在行已经选了，或者所在列已经选好了，那么就不能再选了，反之则可以选。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int c[25],r[100005]; 
char s[25][100005];
int main()
{
	ios::sync_with_stdio(false);
    int n,m,a,b,t,flag;
    
    cin >> t;
    while(t--){
    	flag = 0;
        cin >> n >> m >> a >> b;
        for(int i = 0; i < n; i++){
        	cin >> s[i];
		}
		int k = (1 << n);
		int cnt1 = 0,cnt2;
		for(int i = 0; i < k; i++){
			cnt1 = 0;
			cnt2 = 0;
			memset(c,0,sizeof(c));
			memset(r,0,sizeof(r));
			for(int j = 0; j < n; j++){
				if(i & (1 << j)) cnt1++,c[j] = 1;
			}
			if(cnt1 > a) continue;
			for(int p = 0; p < n; p++){
				if(c[p]) continue;
				for(int j = 0; j < m; j++){
					if(s[p][j] == '*' && !c[p] && !r[j]){
						cnt2++;
						r[j] = 1;
					}
				}
			}
			if(cnt2 <= b){
				cout << "yes\n";
				flag = 1;
				break;
			}
		}
		if(!flag) cout << "no\n";
    }
	return 0;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

vector<int>edge[100005];
ll cnt[100005],val[100005];
void dfs(int s,int f)
{
	int l = edge[s].size();
	//cnt[s] = cnt[f] + 1;
	cnt[s] = 1;
	for(int i = 0; i < l; i++){
		int v = edge[s][i];
		if(v == f) continue;
		dfs(v,s);
		cnt[s] += cnt[v];
	}
}

bool cmp(ll a,ll b)
{
	return a > b;
}

int main()
{
	ios::sync_with_stdio(false);
    int n,u,v;
	cin >> n;
    for(int i = 1; i < n; i++){
    	cin >> u >>  v;
    	edge[u].push_back(v);
    	edge[v].push_back(u);
	}
	dfs(1,0);
	ll sum = 0;
    int  t = 0;
	for(int i = 2; i <= n; i++){
		val[t++] = (n - cnt[i]) * cnt[i];
	}
	sort(val,val+t,cmp);
	for(int i = 1; i < n; i++){
		sum += val[i - 1] * i;
	}
	cout << sum;
	return 0;
}

H-奇怪的背包问题增加了

思路：这个题目要转化成二进制相加才好理解，每个数都是例如10，100，1000...的形式，而最后要等于2^30，也就是10000......,那么最后一次相加结果一定是一个1，后面全是零，如果这m个数的和能大于2^30，那么一定能组合成2^30,按照前面的约束，我们优先从大到小相加，这样可以保证位数增多时一定是第一个数是1，后面全是零(有点贪心的味道)，这样一路加过去肯定可以加到2^30.如果和小于2^30，那么一定不能填满。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct Node{
	int xb;
	ll val;
	bool operator < (const Node &a)const{
	    return val > a.val;
	}
}node[100005];

int main()
{
	ios::sync_with_stdio(false);
    int t,n,m,k;
    cin >> t;
    ll temp = (1 << 30);
    int a[100005];
    while(t--){
    	cin >> m;
    	ll sum = 0;
    	memset(a,0,sizeof(a));
    	for(int i = 1; i <= m; i++){
    		cin >> k;
    		node[i].val = (1 << k);
    		node[i].xb = i;
    		sum += node[i].val;
		}
		if(sum < temp) {
			cout << "impossible\n";
			continue;
		}
		sort(node+1,node+m+1);
		sum = 0;
		for(int i = 1; i <= m; i++){
			sum += node[i].val;
			a[node[i].xb] = 1;
			if(sum == temp){
				break;
			}
		}
		for(int i = 1; i <= m; i++){
			cout << a[i];
		}
		cout << "\n";
	}
	return 0;
}


小白月赛22

D - 收集纸片

思路：因为数据范围不大，所有直接枚举，而我们是要从最开始的位置去往有纸片的位置，然后再到下一个有纸片的位置，这就存在先到哪一个有纸片的位置再到哪一个有纸片的位置，总共有n！种可能，n<=10,所有最多10！种可能，那我们用一个数组去存第几个有纸片的位置，利用next_permutation求出所有排列，计算每种的距离和，求之前我们可以先预处理出每个有纸片的位置到其他有纸片的位置的距离，d[i][0],表示第i个有纸片的横坐标，1则表示纵坐标，len[i][j]表示i-j的距离， 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int d[15][2],len[15][15],a[15],n,k,l,x,y,t,ans;
void solve()
{
	int sum = 0;
	sum = len[0][a[1]];
	for(int i = 2; i <= n; i++){
		sum += len[a[i - 1]][a[i]];
	}
	sum += len[a[n]][0];
	ans = min(ans,sum);
}

int main()
{
	cin >> t;
	while(t--){
		ans = inf;
		memset(len,0,sizeof(len));
		cin >> k >> l;
		cin >> x >> y;
		cin >> n;
		d[0][0] = x;
		d[0][1] = y;
		for(int i = 1; i <= n; i++){
			cin >> d[i][0] >> d[i][1];
			a[i] = i;
		} 
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				len[i][j] = abs(d[i][0] - d[j][0]) + abs(d[i][1] - d[j][1]);
			}
		}
		do{
			solve(); 
		}while(next_permutation(a+1,a+n+1));
		cout << "The shortest path has length " << ans << endl;
	}
	return 0;
}

C-交换游戏

思路：记忆化搜索，在串中找到-oo,oo-的子串，按题意变为o--,--o,记o为1，-为0，串便可以转化为一个数x，且011^111 --> 100可以实现转化,再找出剩余1的个数，用数组保存起来，便是x的答案。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int a[1 << 12];
int dfs(int x)
{
    if(x == 0 || a[x]) return a[x];
    int cnt = 0;
    for(int i = 0; i < 12; i++){
        if((x >> i) & 1) cnt++;
    }
    for(int i = 0; i < 10; i++){
        if(x >> (i+1) & 1 && (x >> i & 1) ^ (x >> (i + 2) & 1)){
            cnt = min(cnt,dfs(x ^ (7 << i)));
        }
    }
    return a[x] = cnt;
}

int main()
{
    int n,x;
    cin >> n;
    char s[15];
    a[0] = 0;
    while(n--){
        cin >> s;
        x = 0;
        for(int i = 0; i < 12; i++){
            x = (x << 1) + (s[i] == 'o' ? 1 : 0);
        }
        cout << dfs(x) << endl;
    }
    return 0;
}

小白月赛19


A-「水」滔天巨浪

思路：设数组dp[i]表示以下标i结尾的以1连续递增的子数组长度，在数组中间部分的话，则要删去dp[i] - 2个，边界的话删去一个，可以先初始化子数组的头是在位置1的情况。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
#define _gcd __gcd
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int a[1005],dp[1005],n;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    a[0] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int len = 1;
    for(int i = 2; i <= n; i++){
    	if(a[i] - 1 == a[i - 1]){
    		len++;
    		break;
		}
	}
	int ans;
	if(a[1] == 1) ans = len - 1;
	dp[1] = 1;
    for(int i = 2; i <= n; i++){
    	dp[i] = (((a[i] - 1) == a[i - 1]) ? dp[i - 1] + 1 : 1);
	}
//	for(int i = 1; i <= n; i++) cout << dp[i] << " ";
//	cout << "\n";
	for(int i = 2; i <= n; i++){
		if(i != n){
			ans = max(ans,dp[i] - 2);
		}
		else{
			if(a[i] == 1000) ans = max(ans,dp[i] - 1);
			else ans = max(ans,dp[i] - 2);
		}
	}
	cout << ans;
    return 0;
}

C-「土」秘法地震: 二维前缀和

思路：因为k*k的这个区域里面不能有1，也就是说k*k这个区域和为0，所有找出所有k*k大小的区域，如果和大于零说明不行。求和可以用二维前缀和来实现。 
#include <bits/stdc++.h>
#include <iostream>
#define LL long long
using namespace std;

char a[1005][1005];
int n,m,q_sum[1005][1005] = {0};
int main()
{
    int k,t = 0;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            q_sum[i][j] = q_sum[i - 1][j] + q_sum[i][j - 1] + a[i][j] - '0' - q_sum[i - 1][j - 1];
        }
    }
    int ans = 0;
    for(int i = k; i <= n; i++){
        for(int j = k; j <= m; j++){
            if(q_sum[i][j] - (q_sum[i - k][j] + q_sum[i][j - k]) + q_sum[i - k][j - k] > 0) ans++; 
        }
    }
    cout << ans;
    return 0;
}

D-「金」初心如金

用cout，cin会超时。
思路：因为每个数都是奇数，且每个数的结果为0或1，所有我们可以利用后面的答案去判断前一个数是不是质数，如果当前数是的结果偶数，又因为每个数都是奇数，奇数到偶数只能是奇数异或1得到，结果是奇数，那么奇数到奇数只能是奇数异或0，也就是可以判断前一个数是否为质数。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
#define _gcd __gcd
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    int n;
    ll x;
    scanf("%d%lld",&n,&x);
    for(int i = 2; i <= n; i++){
    	scanf("%lld",&x);
    	if(!(x%2)) printf("1\n");
    	else printf("0\n");
	}
    return 0;
}


小白月赛18

D-Forsaken喜欢正方形

思路：根据四个点求出四条边和两条对角线，按长度排好序，那么要是正方形的话，数组里第一个数和第四个数相等，最后两个数相等才行。
第一次枚举是第一个点可与其它三个点连接，第二个点可与剩下两个点连接.......。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

struct Node{
	int x,y;
}node[5];

int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool judge()
{
	vector<int>rq;
	int len;
	for(int i = 1; i <= 4; i++){
		for(int j = i + 1; j <= 4; j++){
			len = (node[i].x - node[j].x) * (node[i].x - node[j].x) + (node[i].y - node[j].y) * (node[i].y - node[j].y);
			rq.push_back(len);
		}
	}
	sort(rq.begin(),rq.end());
	if(rq[0] == rq[3] && rq[4] == rq[5]) return true;
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	int n,k;forasken
    for(int i = 1; i <= 4; i++) cin >> node[i].x >> node[i].y;
    if(judge()){
    	cout << "wen";
    	return 0;
	}
	for(int i = 1; i <= 4; i++){
		for(int j = 0; j < 4; j++){
			int t1 = node[i].x;
			int t2 = node[i].y;
			node[i].x += d[j][0];
			node[i].y += d[j][1];
			if(judge()){
				cout << "hai xing";
				return 0;
			}
			node[i].x = t1;
			node[i].y = t2;
		}
	}
	cout << "wo jue de bu xing";
	return 0;
}

G-Forsaken的三位点数：树状数组+二分

时间复杂度：O(nlog2n)
树状数组：


x表示下标为x的节点，val表示加上的值，要a[x]加上val，那么所有能够管辖到x的区间都要加上val, 即 x += lowbit(x)可以依次求到管辖x的区间，都要加上val。
sum函数求1-x的区间和，我们先要加上a[x]自己，然后加上x能管辖的区间的和，x能管辖的区间能管辖的区间的和......，一直到x为零， 
void add(int x,int val)
{
	while(x <= n){
		tree[x] += val;
		x += (x&(-x));
	}
}

int sum(int x){
	int ans = 0;
	while(x){
		ans += tree[x];
		x -= (x&(-x));
	}
	return ans;
}



思路：先算出每个点到原点的距离，设为x，能量值加一，利用树状数组保存起来，如果要求最小球半径包含能量值大于等于k，可以用二分查找，因为半径越大，包含能量值越多，二分查找合适的半径r，sum[r]表示所有长度在[1,r]区间内的能量值和，即半径为r的球所包含的能量值。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

int tree[200005];
void add(int x,int val)
{
	while(x <= 200005){
		tree[x] += val;
		x += (x&(-x));
	}
}

int sum(int x){
	int ans = 0;
	while(x){
		ans += tree[x];
		x -= (x&(-x));
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	int n,op,k,cnt = 0;
	ll x,y,z;
	cin >> n;
	while(n--){
		cin >> op;
		if(op == 1){
			cin >> x >> y >> z;
			double temp = sqrt(x*x + y*y + z*z);
			int p = ceil(temp);
			cnt++;
			add(p,1);
		}
		else{
			cin >> k;
			if(k > cnt) cout << "-1\n";
			else{
				int l = 0,r = 200005,ans = 0;
				while(l <= r){
					int mid = (l + r) / 2;
					if(sum(mid) >= k){
						ans = mid;
						r = mid - 1;
					}
					else l = mid + 1;
				}
				cout << ans << endl;
			}
		}
	}
	return 0;
}

C-forsaken给学生分组

思路：有点贪心的味道，优先让当前数组剩余人数最大与最小的两个到一组去，先看看n按2人一组最多可以分成多少组，假设为x组，如果比k多，那么直接分k组，即大的减去小的k次，如果比k小，且k是偶数，x减去(k-x),再按上面的操作去执行，如果k是奇数，x -= (k-x)+1,再同上。 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	ll n,k,a[100005];
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	ll t = n / 2,i = 1,ans = 0;
	if(k <= t){
		while(k--){
			ans += a[n--] - a[i++];
		}
		cout << ans;
	}
	else{
		t -= (k - t);
		if(n & 1) t++;
		while(t--){
			ans += a[n--] - a[i++];
		}
		cout << ans;
	}
	return 0;
}



小白月赛 文章被收录于专栏

希望通过写小白月赛来提升自己的算法能力。

全部评论

相关推荐

昨天 20:30
门头沟学院 Java
众安大连（26届转正）一面凉经
1、单向链表怎么找到中间节点？（先答了遍历得到长度，再/2找中间节点，后来又说快慢节点）2、设计模式场景题：比如现在有支付宝、微信、各大银行卡等支付方式，最坏的情况是写了20多个if-else判断是用户选择哪种支付方式，耦合度很高，如果叫你优化，你怎么想？（先说责任链模式，但没太接触过设计模式的题，瞎说一气；面试官提醒策略模式）3、还是设计模式场景题：模板方法，比如说有三个模板方法A、B、C，第一个子类我想让他实现ABC这么执行，第二个子类我想让他实现ACB，这个怎么实现？（使用“钩子方法”，抽离一个方法返回true、false，true就ABC，false就ACB）4、DB和redis怎么保...
查看12道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
05-29 15:26
这次是真的告别了！
谢谢大家的鼓励，评论区的哥们说得很对。我们俩真的没有任何问题，只是在当下的这个时机不合适。昨天收到分手的短信后，我一直在整理手机相册，不知不觉拍了好多照片，我都舍不得删掉。一起去海边一起放了风筝一起在食堂吃饭，她把不吃的青菜都夹给我一起庆祝秋招上岸晚上我约她出来见了一面，还是觉得即便要分手，也要好好告别。她很坚强，没有哭，反倒是我有点忍不住，最后我抱了抱她。然后把我之前准备的毕业礼物送给了她，也算分手礼物了。我们都会越来越好的。
贺韦：呜呜呜呜真正的告别从来不是 “一刀两断”，而是 “我承认你曾照亮过我的生命，现在我要目送你去更远的地方”
好好告别我的学生时代 毕业季等于分手季吗
点赞 评论 收藏
分享
05-17 11:07
桂林航天工业学院 运营
一年了
感觉自己素质越来越低了
求offer的大角牛：不吃香菜
点赞 评论 收藏
分享
04-17 00:42
门头沟学院 后端
点赞 评论 收藏
分享
今天 07:40
同济大学 ARM工程师
来喽来喽 嵌入式圣经来喽
儿啊，看你桌上堆满开发板、芯片、杜邦线，像零件摊儿，妈心里堵。示波器探头缠成蜘蛛网，碰一下都怕坏了你“宝贝疙瘩”。你爸叹气：“那板子灯闪啊闪，能闪出房车媳妇孙子？”这些年，家跟着你“低功耗”运行了。妈心疼！你黑眼圈比覆铜厚，头发掉得比BUG多。你爸嘴硬心软：“工资都填开发板坑了吧？比抽烟还费！”上回你生日，他非让多转五百，“这小子肯定又盯上核心板了，别饿着搞开发”。妈知道你想“改变世界”，可身边做嵌入式的，谁真住大别墅了？不都在公司熬着调BUG薅头发？芯片厂吹“万物互联”，就是忽悠你们当“电子民工”！小时候拆收音机多爱笑，现在眉头夹死蚊子，念叨“时序不对”、“内存泄漏”，破板子害的！嵌入式光靠...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的实习收获 #
9268次浏览 189人参与
# TP-LINK工作体验 #
46732次浏览 825人参与
# 实习吐槽大会 #
11697次浏览 52人参与
# 我的租房踩坑经历 #
1711次浏览 45人参与
# 晒一晒你的工位 #
77945次浏览 262人参与
# 你的办公桌上都有什么？ #
6310次浏览 52人参与
# 入职第三天，晒晒你的工位 #
30909次浏览 147人参与
# 实习中的菜狗时刻 #
359828次浏览 3274人参与
# 工作压力大怎么缓解 #
78127次浏览 929人参与
# 机械制造2023笔面经 #
115917次浏览 747人参与
# 今年形式下双非本找得到工作吗 #
137969次浏览 1042人参与
# Offer比较，求稳定还是求发展 #
52389次浏览 248人参与
# 电网笔面经互助 #
33259次浏览 331人参与
# 来选选带哪个offer回家过年 #
659670次浏览 5271人参与
# 机械专业只有考研才有出路吗 #
104343次浏览 866人参与
# 薪资一样，你会选择去大厂还是小公司 #
19291次浏览 116人参与
# 24届的你们现状如何了？ #
69557次浏览 399人参与
# 你觉得机械有必要实习吗 #
50794次浏览 445人参与
# 我的第一份实习怎么找的 #
102583次浏览 1020人参与
# 你的秋招第一场笔试是哪家 #
129418次浏览 1404人参与
牛客网
牛客企业服务