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];

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));
tot = 0;
}

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

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;
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);
}
}
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;
}
```