Noip2016 ysy模拟1

tonyfang posted @ 2016年11月16日 18:29 in 随笔 with tags c++ OI , 968 阅读

1. chess

第一轮,A在(0,0)放棋子。

第二轮,B在每个(x,y)放棋子,满足(x-2,y)或(x-1,y-1)有且仅有1个是A的棋子。

第三轮,A每个(x,y)放棋子,满足(x-2,y)或(x-1,y-1)有且仅有1个是B的棋子。

重复上述过程(2,3),问第t轮后(x0,y0)~(x0+w, y0+h)的棋子情况(A,B,空)

$0\leq t, x0, y0 \leq 10^{12}, 0 \leq w,h \leq 50$

【题解】

有可能有棋子的只可能是点(x,y),其中x+y为偶数,然后按照(x+y)/2的奇偶性来判断是什么棋子。

然后按照上述规律排列每个棋子,发现C(n,m)为偶数的时候是空格。

如何判断C(n,m)是不是偶数?

如果n&m==m,那么C(n,m)是奇数。

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 60;

int w, h;
ll t, x, y;

char s[M][M];

int main() {
	freopen("chess.in", "r", stdin);
	freopen("chess.out", "w", stdout);
	scanf("%lld%lld%lld%d%d", &t, &x, &y, &w, &h);
	
	for (int i=0; i<w; ++i)
		for (int j=0; j<h; ++j) {
			ll newx = x+i, newy = y+j;
//			printf("%lld %lld\n", newx, newy);
			ll ss = newx + newy;
			if(ss&1) s[i][j] = '.';
			else {
				ss=ss>>1;
				if(ss+1<=t) {
//					printf("ss=%lld\n", ss);
					if(ss&1) s[i][j] = 'B';
					else s[i][j] = 'A';
					if((ss&newy) != newy) s[i][j] = '.';
				} else s[i][j] = '.';
			}
		}
	for (int i=h-1; i>=0; --i, puts(""))
		for (int j=0; j<w; ++j)
			printf("%c", s[j][i]);
	
	return 0;
}

// 5 4 1 3 4

2. shop

给出n个点m条边的无向图,标号为0~n-1,其中前p个点有商店,每个商店在l[i]-r[i]时间卖钻石,你需要花t[i]的时间买钻石,求你最多获得钻石数量。

$n, m \leq 50, p \leq 16$。

【题解】

状态压缩,$O(2^{p}pn)$。

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 60;

ll f[1<<18][M];

int n, m, p;
ll dis[M][M];

int l[M], r[M], t[M];

int main() {
	freopen("shop.in", "r", stdin);
	freopen("shop.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &p);
	for (int i=0; i<n; ++i) {
		for (int j=0; j<n; ++j)
			dis[i][j] = 1ll<<40;
		dis[i][i] = 0;
	}
	for (int i=0; i<(1<<p); ++i)
		for (int j=0; j<n; ++j) f[i][j] = 1ll<<40;
	for (int i=1; i<=m; ++i) {
		int u, v;
		ll c;
		scanf("%d%d%lld", &u, &v, &c);
		dis[u][v] = min(dis[u][v], c);
		dis[v][u] = min(dis[v][u], c);
	}
	for (int k=0; k<n; ++k)
		for (int i=0; i<n; ++i)
			for (int j=0; j<n; ++j)
				dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
	for (int i=0; i<p; ++i) scanf("%d%d%d", &l[i], &r[i], &t[i]);
	f[0][n-1]=0;
	int ans = 0;
	for (int i=1; i<(1<<p); ++i) {
		int mx=0;
		for (int j=0; j<p; ++j) {
			if(i&(1<<j)) {
				++mx;
				for (int k=0; k<n; ++k)
					if(f[i^(1<<j)][k]+dis[j][k]<=r[j])
						f[i][j] = min(f[i][j], max((ll)l[j], f[i^(1<<j)][k]+dis[j][k])+t[j]);
			}
		}
		for (int j=0; j<n; ++j) {
			if(f[i][j] < (1ll<<40)) 
				ans = max(ans, mx);
		}
	}
	printf("%d\n", ans);
	return 0;
}

3. sequence

最大m子段和。

$m \leq n \leq 10^5, a_i \leq 10^9$。

【题解】

合并每个正段和负段。0合并到正段。然后用堆维护正负段(删除正段,加入负段)。

# include <stdio.h>
# include <algorithm>
# include <set>
# include <iostream>
# include <string.h>
# define abs(x) (x>0?x:-x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 1000010;

int n, m;
ll a[M];

ll b[M];
int bn=0;
int S[M];
int fs[M], fsn=0;

struct node {
	ll cur;
	int id;
};

bool operator <(node a, node b) {
	return a.cur>b.cur;
}

set<node> s;

int fa[M];
int fl[M], fr[M];

inline int getf(int x) {
	return fa[x]==x ? x : fa[x] = getf(fa[x]);
}

inline void unions(int fx, int fy) {
	fa[fx] = fy;
	fl[fy] = min(fl[fy], fl[fx]);
	fr[fy] = max(fr[fy], fr[fx]);
}

int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	while(~scanf("%d%d", &n, &m)) {
		memset(b,0,sizeof(b));
		memset(S,0,sizeof(S));
		s.clear();
		bn=fsn=0;
		for (int i=1; i<=n; ++i) scanf("%lld", &a[i]);
		int head=1, tail=n;
		while(a[head]<0) ++head;
		while(a[tail]<0) --tail;
		int zf=1;
		++bn;
		for (int i=head; i<=tail; ++i) {
			if(zf*a[i]>0 || (zf==1&&a[i]==0)) {
				b[bn]+=a[i];
				S[bn]++;
			} else {
				++bn;
				b[bn]=a[i];
				S[bn]=1;
				zf=-zf;
			}
		}
		int total1=0, total2=0;
		ll tot=0;
		for (int i=1; i<=bn; ++i) {
			if(b[i]>=0) {
				total1+=S[i];
				total2++;
				tot+=b[i];
			}
		}
		if(m >= total2 && m <= total1) {
			printf("%lld\n", tot);
		} else if(m > total1) {
			sort(a+1, a+n+1);
			ll ans=0;int k=0;
			for (int i=n;i>=1;--i) {
				++k;
				ans+=a[i];
				if(k==m)break;
			}
			printf("%lld\n", ans);
		} else if(m < total2) {
			for (int i=1; i<=bn; ++i) {
				b[i]=-abs(b[i]);
				s.insert((node){b[i],i});
			}
			int res = total2 - m;
			for (int i=1; i<=bn; ++i) fa[i] = i, fl[i] = fr[i] = i;
			for (int i=1; i<=res; ++i) {
				node x = *s.begin();
				s.erase(x);
				int fx = x.id, fll = fl[fx], frr = fr[fx];
				tot=tot+x.cur;
				int left=-1,right=-1;
				if(fll > 1) left=getf(fll-1);
				if(frr < bn) right=getf(frr+1);
				b[fx]=-b[fx];
				if(left!=-1) {
					s.erase((node){b[left], left});
					unions(left, fx);
					b[fx]+=b[left];
				}
				if(right!=-1) {
					s.erase((node){b[right], right});
					unions(right, fx);
					b[fx]+=b[right];
				}
				if(left!=-1 && right!=-1)
					s.insert((node){b[fx],fx});
			}
			printf("%lld\n", tot);
		}
	}
	
	return 0;
}

 

Gujarat STD-1 Model 说:
2022年9月11日 17:01

Gujarat State Department of School Education, Gandhinagar and the State level subject experts and other private school teaching staff of the Elementary Level Primary School have designed and suggested the GSEB 1st Class Model Paper 2023 with sample answers Set wide as SET-A, SET-B, SET-C and SET-D to know the new exam scheme or question pattern. Gujarat STD-1 Model Paper Students of the Gujarat state can download the NCERT & SCERT Syllabus GSEB STD-1 Question Paper 2023 Pdf with sample answers along with the class teacher’s suggested all lesson or chapter’s most important questions for Part-A, Part-B, Part-C and Part-D exams of Term-1 & Term-2 to the academic year of 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter