【弱校胡策】 2016 noip模拟赛题解
|
432
|
noip&&noi,spfa,分层图,图论,差分约束,快速幂,数据结构,模拟,算法,线段树,贪心
|
Dewct

43 字
|
几秒读完

Day 1 T 1:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[101];
int main()
{
	freopen("hungry.in","r",stdin);
	freopen("hungry.out","w",stdout);
	f[1] = 1 , f[2] = 2;
	for(int i =  3 ; i <= 60 ; i ++)
		f[i] = f[i-1] + f[i-2];
	int n;
	scanf("%d",&n);
	printf("%lld\n",f[n]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Day 1 T 2

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int l[15001], r[15001], w[15001], w0[15001], d[2501], a[2501];
int n,m,tot;
int tmp;
void graphinit(){ tot = 0;}
void add( int a, int b, int c){
	tot++;
	l[tot] = a; r[tot] = b; w[tot] = c;
}
bool bellman(){
	bool flag;
	memset(d, 0, sizeof(d));
	d[0] = 0;
	for(int i = 0; i <= n; ++i){
		flag = false;
		for(int j = 1; j <= tot; ++j)
			if(d[l[j]] + w[j] < d[r[j]]){
				flag = true;
				d[r[j]] = d[l[j]] + w[j];
			}
		if(!flag)return true;
	}
	return false;
}
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
	scanf("%d%d", &n, &m); n++;
	graphinit();
	for(int i = 1; i <= m; ++i){
		int j, k, p, q;
		scanf("%d%d%d%d", &j, &k, &p, &q);
		if(p == 1) add(j+k, j-1, -q-1);
		else add(j-1, j+k, q-1);
	}
	if(bellman()) printf("YES");
	else printf("NO");
	fclose(stdin);
	fclose(stdout);
	return 0;
}

ps:附上我的随机输出^0^

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
int orz[105], lll[105][105];
bool sq[105][105];
typedef long long ll;
struct qer
{
	int li,ni,vi,ki;
}qq[105];
int main()
{
	freopen("seq.in", "r", stdin);
	freopen("seq.out", "w", stdout);
	int n, m;
	cin>>n>>m;
	int ans = 0;
	for(int i = 1;i <= m;i ++)
	{
		scanf("%d%d%d%d", &qq[i].li, &qq[i].ni, &qq[i].vi, &qq[i].ki);
		qq[i].ni += qq[i].li;
		if(sq[qq[i].li][qq[i].ni] != qq[i].vi && i != 1 && lll[qq[i].li][qq[i].ni] == qq[i].ki)
		{
			cout<<"NO"<<endl;
			return 0;
		}
		lll[qq[i].li][qq[i].ni] = qq[i].ki;
		sq[qq[i].li][qq[i].ni] = qq[i].vi;
	}
	srand(time(0));
	if(rand()%2 == 0)
	cout<<"YES"<<endl;
	else
	cout<<"NO"<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Day 1 T 3

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#define KILL puts("haha");
#define L(x) (x << 1)
#define R(x) (x << 1 | 1)
#define sz(x) (tree[p].r - tree[p].l + 1)
using namespace std;
const int MAXN = 100000 + 5;
struct treedot
{
	int l,r;
	int fz;
	int num;
	bool qf;
}tree[MAXN << 2];
void spread(int p)
{
	int fz = tree[p].fz,qf = tree[p].qf;
	tree[p].fz = -1;
	tree[p].qf = false;
	if(tree[p].l == tree[p].r)
	{
		if(fz != -1)
			tree[p].num = fz;
		tree[p].num ^= qf;
		return;
	}
	if(fz != -1)
	{
		tree[L(p)].fz = tree[R(p)].fz = fz;
		tree[L(p)].qf = tree[R(p)].qf = false;
	}
	tree[L(p)].qf ^= qf;
	tree[R(p)].qf ^= qf;
	return;
}
void build(int p,int l,int r)
{
	tree[p].l = l;
	tree[p].r = r;
	tree[p].fz = -1;
	if(l == r)
		return;
	int mid = (tree[p].l + tree[p].r) >> 1;
	build(L(p),l,mid);
	build(R(p),mid + 1,r);
	return;
}
void change(int p,int l,int r,int v)
{
	spread(p);
	if(l <= tree[p].l && tree[p].r <= r)
	{
		if(v == -1)
			tree[p].qf ^= 1;
		else
			tree[p].fz = v;
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if(l <= mid)change(L(p),l,r,v);
	if(mid <  r)change(R(p),l,r,v);
	return;
}
void qf(int p,int l,int r)
{
	change(p,l,r,-1);
	return;
}
int ask(int p,int x)
{
	spread(p);
	if(tree[p].l == x && x == tree[p].r)
		return tree[p].num;
	int mid = (tree[p].l + tree[p].r) >> 1;
	if(x <= mid)return ask(L(p),x);
	if(mid <  x)return ask(R(p),x);
}
char q[MAXN];
void scanf(int &x,int &i)
{
	while(!isdigit(q[i]))
		i ++;
	x = 0;
	while(isdigit(q[i]))
	{
		x = (x << 1) + (x << 3) + q[i] - '0';
		i ++;
	}
	return;
}
int l,r;
int main()
{
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	int n = 95533;
	build(1,1,n);
	while(gets(q))
	{
		bool flag;
		int now = 2;
		flag = q[now] == '(';
		scanf(l,now);
		l += flag;
		scanf(r,now);
		flag = q[now] == ')';
		r -= flag;
		switch(q[0])
		{
			case 'U':change(1,l,r,1);break;
			case 'I':change(1,1,l - 1,0);change(1,r + 1,n,0);break;
			case 'D':change(1,l,r,0);break;
			case 'C':change(1,1,l - 1,0);change(1,r + 1,n,0);qf(1,l,r);break;
			case 'S':qf(1,l,r);break;
		}
	}
	bool flag = true;
	for(int i = 1;i <= n;i ++)
	{
		if(ask(1,i))
		{
			l = i;
			i ++;
			while(i <= n && ask(1,i))
				i ++;
			r = i - 1;
			flag = false;
			printf("[%d,%d] ",l,r);
		}
	}
	if(flag)
		puts("empty!!!");
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Day 2 T 1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int size = 200100;
ll num[size];
int n,m;
bool check(ll mid)
{
	int tot = 0;
	if(n)
		tot = 1;
	ll now = 0;
	for(int i = 1 ; i <= n ; i ++)
	{
		while(now + num[i] > mid)
		{
			tot ++;
			now = 0;
			if(tot > m)
				return false;
		}
		now += num[i];
	}
	if(tot <= m)
		return true;
	return false;
}
int main()
{
	freopen("daze.in","r",stdin);
	freopen("daze.out","w",stdout);
	scanf("%d%d",&n,&m);
	ll l = 1 , r = 0;
	for(int i = 1 ; i <= n ; i ++)
		scanf("%lld",&num[i]) , r += num[i];
	r ++;
	while(r - l > 1)
	{
		ll mid = (l + r) / 2;
		if(check(mid))
			r = mid;
		else
			l = mid;
	}
	printf("%lld\n",r);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Day 2 T 2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int size = 2010;
int num[size];
int dp[size][size];
int n,mod;
int main()
{
	freopen("dp.in","r",stdin);
	freopen("dp.out","w",stdout);
    scanf("%d%d",&n,&mod);
    for(int i = 1 ; i <= n ; i ++)
        scanf("%d",&num[i]);
    for(int i = 1 ; i <= n ; i ++)
    {
    	for(int j = 0 ; j < mod ; j ++)
    	{
    		dp[i][j] = dp[i-1][j];
    		int p = ( j + mod - num[i] % mod) % mod;
    		if(dp[i-1][p] || p == 0)
    		{
    			dp[i][j] = max(dp[i][j],dp[i-1][p] + num[i]);
    		}
    	}
    }
    printf("%d\n",dp[n][0]);
    fclose(stdin);
	fclose(stdout);
    return 0;
}

Day 2 T 3

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=2010,SIZEM=10010,SIZEGN=220010,INF=0x7fffffff/2;
int GN;//0~N-1
vector<pair<int,int> > c[SIZEGN];
int f[SIZEGN];
bool inq[SIZEGN];
queue<int> Q;
void addedge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
}
int SPFA(int S,int T){
	for(int i=0;i<GN;i++) f[i]=INF;
	memset(inq,0,sizeof(inq));
	while(!Q.empty()) Q.pop();
	f[S]=0;inq[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			if(f[x]+c[x][i].second<f[u]){
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
	return f[T];
}
int N,M,C;
class EDGE{
public:
	int u,v,h,w;
	int l,r;
};
EDGE edges[SIZEM];
vector<int> legal[SIZEN];
int sum[SIZEN];
void unique(vector<int> &s){
	sort(s.begin(),s.end());
	int tot=0;
	for(int i=0;i<s.size();i++){
		if(!i||s[i]!=s[i-1]) s[tot++]=s[i];
	}
	while(s.size()>tot) s.pop_back();
}
void mark_legal_height(void){//计算每个节点的合法高度
	legal[0].push_back(0);
	legal[N-1].push_back(0);
	for(int i=0;i<M;i++){
		edges[i].l=edges[i].h-(C/2),edges[i].r=edges[i].h+(C/2);
		edges[i].l=max(edges[i].l,0);
		for(int j=edges[i].l;j<=edges[i].r;j++){
			legal[edges[i].u].push_back(j);
			legal[edges[i].v].push_back(j);
		}
	}
	for(int i=0;i<N;i++) unique(legal[i]);
	sum[0]=0;
	for(int i=1;i<N;i++) sum[i]=sum[i-1]+legal[i-1].size();
}
int hash1(int i,int j){//i处的第j个合法高度
	return sum[i]+j;
}
int hash2(int i,int h){//i处高度为h
	return sum[i]+lower_bound(legal[i].begin(),legal[i].end(),h)-legal[i].begin();
}
void makegraph(void){
	GN=sum[N-1]+legal[N-1].size();
	for(int i=0;i<N;i++){
		for(int j=0;j+1<legal[i].size();j++){
			//爬升有花费,下降没有
			addedge(hash1(i,j),hash1(i,j+1),(legal[i][j+1]-legal[i][j])*C);
			addedge(hash1(i,j+1),hash1(i,j),0);
		}
	}
	for(int i=0;i<M;i++){
		for(int j=edges[i].l;j<=edges[i].r;j++){
			int a=hash2(edges[i].u,j),b=hash2(edges[i].v,j);
			int w=(edges[i].h-j)*(edges[i].h-j)+edges[i].w;
			addedge(a,b,w);
			addedge(b,a,w);
		}
	}
}
void read(void){
	scanf("%d%d%d",&N,&M,&C);
	for(int i=0;i<M;i++){
		scanf("%d%d%d%d",&edges[i].u,&edges[i].v,&edges[i].h,&edges[i].w);
	}
}
int main(){
	freopen("marisa.in","r",stdin);
	freopen("marisa.out","w",stdout);
	read();
	mark_legal_height();
	makegraph();
	printf("%d\n",SPFA(hash1(0,0),hash2(N-1,0)));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 
下载：题目数据
 
 

上一篇
下一篇