频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
CSU Monthly 2013 Oct 中南大学ACM月赛
2014-03-10 11:05:50         来源:CSU Monthly 2013 Oct 中南大学ACM月赛  
收藏   我要投稿

题目很好,比较活跃,有难度,同时对基础要求又比较好,总体感觉这题目做起来挺不错的,没做出的去补一下


https://acm.csu.edu.cn/OnlineJudge/problem.php?id=1318


数学题:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

int main() {
	ll n;
	while(scanf("%lld",&n) == 1) {
		ll ans = 1;
		ll num = 1;
		while((num*2) - 1 < n) {
			ans++;
			num *= 2;
		}
		printf("%lld\n",ans);
	}
	return EXIT_SUCCESS;
}



https://acm.csu.edu.cn/OnlineJudge/problem.php?id=1321

spfa,记录最短路径的同时记录妹子的数量


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

int n,m;

bool vis[10000 + 5];
int dis[10000 + 5];
int ans[10000 + 5];
int num [10000 + 5];
int head[10000 + 5];

typedef struct Node {
	int from,to;
	int nex;
	int w;
};

Node edge[100000 + 5];
int tot;

void clear() {
	memset(num,0,sizeof(num));
	memset(edge,0,sizeof(edge));
	memset(head,-1,sizeof(head));
	tot = 0;
}

void add(int u,int v,int w) {
	edge[tot].from = u;
	edge[tot].to = v;
	edge[tot].nex = head[u];
	edge[tot].w = w;
	head[u] = tot++;
}

int spfa(int s,int e) {
	memset(vis,false,sizeof(vis));
	for(int i=0;i<=n;i++) 
		dis[i] = inf;
	for(int i=1;i<=n;i++)
		ans[i] = inf;
	dis[s] = 0;
	ans[s] = num[s];
	vis[s] = true;
	queue q;
	q.push(s);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i=head[u];i!=-1;i=edge[i].nex) {
			int v = edge[i].to;
			if(dis[u] + edge[i].w < dis[v]) {
				dis[v] = edge[i].w + dis[u];
				ans[v] = ans[u] + num[v];
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
			else if(dis[v] == dis[u] + edge[i].w) {
				if(ans[v] < ans[u] + num[v]) {
					ans[v] = ans[u] + num[v];
					if(!vis[v]) {
						vis[v] = true;
						q.push(v);
					}
				}
			}
		}
	}
	if(dis[n] == inf) 
		return -1;
	else
		return ans[n];
}

int main() {
	while(scanf("%d %d",&n,&m) == 2) {
		clear();
		for(int i=1;i<=n;i++)
			scanf("%d",&num[i]);
		for(int i=1;i<=m;i++) {
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		int answer = spfa(1,n);
		printf("%d\n",answer);
	}
	return EXIT_SUCCESS;
}


https://acm.csu.edu.cn/OnlineJudge/problem.php?id=1320


仔细写几个,不能遗漏,发现是卡特兰数,因为要取模 涉及到整除问题,所以要用扩展欧几里德求乘法逆元来避免这个问题


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

const ll MOD = 1000000007;

ll dp[10000 + 5];

ll n;

ll exgcd(ll a, ll b, ll &x, ll &y)  {
	if(!b) {
		x = 1; y = 0;
		return a;
	}
	ll r = exgcd(b, a%b, y, x);
	y -= a/b*x;
	return r;
}

ll inv(ll a, ll m) //求逆元直接模版套上 
{
	ll x,y,gcd = exgcd(a, m, x, y);
	if(x < 0)  
		x += m;
	return x;
}

void clear() {
	memset(dp,0,sizeof(dp));
	dp[1] = 1;
	dp[2] = 2;
	for(int i=3;i<10001;i++) {
		dp[i] = ((dp[i-1]*(4*i-2)%MOD) * ((inv(i+1,MOD) + MOD)%MOD))%MOD;
	}
}

int main() {
	clear();
	while(scanf("%lld",&n) == 1) {
		printf("%lld\n",dp[n]);
	}
	return EXIT_SUCCESS;
}

https://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326

符合分组背包,所以用分组背包做一下,注意分组要求

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;


vector G[1000 + 5];

int n,V,q;

int dp[1000 + 5];
int p[1000 + 5],w[1000 + 5];
int father[1000 + 5];

void clear() {
	memset(dp,0,sizeof(dp));
	for(int i=0;i<1005;i++)
		father[i] = i;
	for(int i=0;i<1005;i++)
		G[i].clear();
}

int find(int x) {
	if(father[x] != x)
		return find(father[x]);
	return x;
}

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

int main() {
	while(scanf("%d %d %d",&n,&V,&q) == 3) {
		clear();
		for(int i=0;i=w[i];j--) 
				if (dp[j - w[i]] + p[i] > dp[j])
					dp[j] = dp[j - w[i]] + p[i];
		}
		for (int i=0;i=0;k--) {
				for (int j=0;j k) 
						continue;
					if (dp[k - w[G[i][j]]] + p[G[i][j]] > dp[k])
						dp[k] = dp[k - w[G[i][j]]] + p[G[i][j]];
				}
			}
		}
		printf("%d\n",dp[V]);
	}
	return EXIT_SUCCESS;
}




点击复制链接 与好友分享!回本站首页
相关TAG标签 中南大学
上一篇:HDU 4762 Cut the Cake(概率+推理+高精度)
下一篇:HDU 4764 Stone(博弈+推理)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站