中南大学的月赛，做了一下，感觉题目很好，没做出的 继续补出来
CSU 1303
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-8
#define inf 0xfffffff
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
string s;
ll exgcd(ll a,ll &x,ll b,ll &y) {
if(b==0) {
x=1;
y=0;
return a;
}
ll r=exgcd(b,x,a%b,y);
ll tmp=x;
x=y;
y=tmp-a/b*y;
return r;
}
int main() {
while(cin>>s) {
int i = 2;
ll a =0;
ll b = 1;
ll c = 0;
ll d = 1;
while(s[i] != ‘(‘) {
a = a*10 + s[i] - ‘0‘;
i++;
b *= 10;
}
i++;
while(s[i] != ‘)‘) {
c = c*10 + s[i] - ‘0‘;
i++;
d *= 10;
}
d--;
ll fanzi = a*d + c;
ll fenmu = b*d;
if(fenmu == 0) {
fanzi = a;
fenmu = b;
}
ll x = 1,y = 1;
ll gcd = exgcd(fanzi,x,fenmu,y);
fanzi /= gcd;
fenmu /= gcd;
printf("%lld/%lld\n",fanzi,fenmu);
}
return EXIT_SUCCESS;
}
csu1307
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-8
#define inf 0xfffffff
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
int n,m,A,B;
typedef struct Node{
int from,to;
int nex;
int w;
};
Node edge[50000 + 5],node[50000 + 5];
int head[2000 + 5];
int dis[2000 + 5];
int tot;
void add(int u,int v,int value) {
edge[tot].from = u;
edge[tot].to = v;
edge[tot].w = value;
edge[tot].nex = head[u];
head[u] = tot++;
}
void clear() {
memset(edge,0,sizeof(edge));
memset(head,-1,sizeof(head));
tot = 0;
}
int spfa(int s,int e) {
for(int i=0;i<=n;i++)
dis[i] = inf;
queue<int> q;
dis[s] = 0;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
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] = dis[u] + edge[i].w;
if(v != e)
q.push(v);
}
}
}
return dis[e];
}
int cal(int x) {
clear();
for(int i=0;i<m;i++) {
if(node[i].w <= x) {
add(node[i].from,node[i].to,node[i].w);
add(node[i].to,node[i].from,node[i].w);
}
}
int ans = spfa(A,B);
return ans;
}
int main() {
while(scanf("%d %d %d %d",&n,&m,&A,&B) == 4) {
for(int i=0;i<m;i++)
scanf("%d %d %d",&node[i].from,&node[i].to,&node[i].w);
int ans;
int l = 0,r = 100000;
while(l < r) {
int mid = (l + r)/2;
if(cal(mid) < inf) {
ans = cal(mid);
r = mid - 1;
}
else
l = mid + 1;
}
printf("%d\n",ans);
}
return EXIT_SUCCESS;
}
/*
3 3 1 2
1 2 80
1 3 40
2 3 50
3 3 1 2
1 2 90
1 3 10
2 3 20
4 5 1 4
1 2 8
1 4 9
1 3 10
2 4 7
3 4 8
*/csu1313
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-8
#define inf 0xfffffff
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
const int MOD = 10000;
typedef struct Matrix{
int m[6][6];
};
Matrix b,c,per;
void clear() {
memset(per.m,0,sizeof(per.m));
per.m[0][1] = 1;
per.m[1][0] = 3;
per.m[1][2] = 1;
per.m[2][0] = 2;
per.m[2][3] = 1;
per.m[3][0] = 1;
per.m[3][4] = 1;
per.m[4][5] = 1;
}
Matrix multi(Matrix a,Matrix b) {
Matrix c;
for(int i=0;i<6;i++) {
for(int j =0;j<6;j++) {
c.m[i][j] = 0;
for(int k=0;k<6;k++)
c.m[i][j] += (a.m[i][k] * b.m[k][j])%MOD;
c.m[i][j] %= MOD;
}
}
return c;
}
Matrix quick(int k) {
Matrix ans = b;
Matrix p = per;
while(k) {
if(k&1) {
ans = multi(ans,p);
k--;
}
else {
k >>= 1;
p = multi(p,p);
}
}
return ans;
}
void Print() {
for(int i=0;i<6;i++) {
for(int j=0;j<6;j++)
printf("%d ",per.m[i][j]);
puts("");
}
}
int main() {
clear();
int Case = 0;
int n;
while(scanf("%d",&n) == 1) {
for(int i=0;i<6;i++)
for(int j=0;j<6;j++)
b.m[i][j] = (i == j);
Matrix ans;
memset(ans.m,0,sizeof(ans.m));
b.m[0][0] = 2;
b = quick(n);
int sum = 0;
for(int i=0;i<6;i++) {
sum += b.m[0][i];
sum %= MOD;
}
printf("Case %d: %d\n",++Case,sum);
}
return EXIT_SUCCESS;
}#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-8
#define inf 0xfffffff
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
int n,k,a,b,q;
int ans[3000 + 5];
struct Node {
int t,d;
Node() {};
Node(int a,int b) {
t = a,d = b;
}
bool operator<(const Node &b) const{
return (d - t * a) < (b.d - b.t * a);
}
};
priority_queue <Node> Q;
void clear() {
memset(ans,0,sizeof(ans));
while(!Q.empty())
Q.pop();
}
int main() {
while(scanf("%d %d %d %d",&n,&k,&a,&b) == 4) {
clear();
int sum = 0;
for(int i=0;i<n;i++) {
int x;
scanf("%d",&x);
if(x <= k)
Q.push(Node(0,x));
else
sum++;
}
for(int i=1;i<=200;i++) {
ans[i] = sum;
if(sum > 0) {
Q.push(Node(i-1,0));
sum--;
}
while(!Q.empty()) {
Node tmp = Q.top();
if(tmp.d + (i - tmp.t) *a <= k)break;
sum++;
Q.pop();
}
}
scanf("%d",&q);
while(q--) {
int x;
scanf("%d",&x);
printf("%d\n",ans[x]);
}
}
return EXIT_SUCCESS;
}
中南大ACM月赛：CSU Monthly 2013 Aug,布布扣,bubuko.com
原文：http://blog.csdn.net/yitiaodacaidog/article/details/20653065