贴一下比赛的代码, 其中 I 题代码源于final大神 ok_again
http://acm.hust.edu.cn/vjudge/contest/127444#overview
I
/*************************************************************************
> File Name: a.cpp
> Author: ok_again
************************************************************************/ #include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio> #define CLR(a, b) memset(a, b, sizeof(a))
using namespace std; const int MOD = ;
const int maxn = ; struct Node {
int a, b, id;
Node() { }
Node(int a, int b, int id)
:a(a), b(b), id(id) { }
bool operator < (const Node& rhs) const {
return a > rhs.a || (a == rhs.a && id < rhs.id);
}
}; vector<Node> lvl[];
vector<int> out; int dp[][maxn][];
pair<int, int> last[][maxn][]; void getout(int st, int c, int k) {
if(k == || st == ) return ;
int l = last[st][c][k].first, j = last[st][c][k].second;
for(int i = ; i < j; i ++) {
out.push_back(lvl[l][i].id);
}
getout(st - , c - l * j, k - j);
} int main() {
int n, k;
while(scanf("%d%d", &n, &k) != EOF) {
for(int i = ; i <= ; i ++)
lvl[i].clear();
for(int i = ; i <= n; i ++) {
int a, b;
scanf("%d%d", &a, &b);
lvl[a - b + ].push_back(Node(a, b, i));
}
for(int i = ; i <= ; i ++)
sort(lvl[i].begin(), lvl[i].end());//, printf("%d --\n", i);
CLR(dp, -);
CLR(last, -);
dp[][][] = ;
for(int i = ; i <= ; i ++) {
int sum = ;
for(int j = ; j <= min(k, (int)lvl[i].size()); j ++) {
//printf("%d -- %d\n", i, j);
int c = j * i;
if(j) sum += lvl[i][j - ].a;
for(int s = ; s >= c; s --) {
for(int t = k; t >= j; t --) {
if(dp[i][s - c][t - j] == -) continue;
if(dp[i + ][s][t] < dp[i][s - c][t - j] + sum) {
dp[i + ][s][t] = dp[i][s - c][t - j] + sum;
last[i + ][s][t] = make_pair(i, j);
}
}
}
}
}
int A, B;
out.clear();
for(int i = ; ; i ++) {
int c = k * ;
if(dp[][c + i][k] != -) {
A = dp[][c + i][k];
B = A - i;
if(dp[][c - i][k] == -) {
getout(, c + i, k);
break;
} else {
if(dp[][c - i][k] * + i > A * - i) {
A = dp[][c - i][k];
B = A + i;
getout(, c - i, k);
break;
}
getout(, c + i, k);
break;
}
} else if(dp[][c - i][k] != -) {
A = dp[][c - i][k];
B = A + i;
getout(, c - i, k);
break;
}
}
sort(out.begin(), out.end());
printf("%d %d\n", A, B);
for(int i = ; i < out.size(); i ++)
printf("%d%c", out[i], i == k - ? '\n' : ' ');
}
return ;
}
A
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e5+;
int n;
int a[M];
int b[M];
int c[M];
int d[M];
int get(int s[]){
sort(s,s+);
return s[];
}
int solve(){
d[]=get(a);
d[]=get(b);
d[]=get(c);
return get(d);
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
while(~scanf("%d",&a[])){
for(int i=;i<;i++){
scanf("%d",&a[i]);
}
for(int i=;i<;i++){
scanf("%d",&b[i]);
}
for(int i=;i<;i++){
scanf("%d",&c[i]);
}
printf("%d\n",solve());
}
return ;
}
B
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e5+;
int n;
char a[][];
vector<int> answer;
int to[];
int area[];
void solve(){
for(int i=;i<;i++){
to[i]=i;
area[i]=;
}
answer.clear();
for(int i=;i<n;i++){
if(a[i][]=='w'){
char c='a';
for(int j=;a[i][j];j++){
if(a[i][j]!='(') continue;
c=a[i][j+];
break;
}
answer.push_back(area[to[c-'a']]);
continue;
}
if(isdigit(a[i][])){
area[to[a[i][]-'a']]=a[i][]-'';
continue;
}
if(a[i][]==':'&&a[i][]=='='){
to[a[i][]-'a']=to[a[i][]-'a'];
continue;
}
int x=a[i][]-'a';
int y=a[i][]-'a';
area[to[x]]=area[to[y]];
}
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
while(~scanf("%d",&n)){
for(int i=;i<n;i++){
scanf("%s",a[i]);
}
solve();
for(int i=;i<answer.size();i++){
printf("%d\n",answer[i]);
}
}
return ;
}
E
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e1+;
int n,m,sx,sy;
char answer[M*M];
bool tabu[M][M];
int dx[]={,,-,};
int dy[]={,-,,};
char type[]="DLUR";
bool inside(int x,int y){
return x>=&&x<=n&&y>=&&y<=m;
}
void solve(){
mt(tabu,false);
int step=;
tabu[sx][sy]=true;
while(true){
bool cango=false;
for(int i=;i<;i++){
int tx=sx+dx[i];
int ty=sy+dy[i];
if(!inside(tx,ty)) continue;
if(tabu[tx][ty]) continue;
cango=true;
tabu[tx][ty]=true;
sx=tx;
sy=ty;
answer[step++]=type[i];
break;
}
if(cango) continue;
answer[step]=;
return ;
}
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
while(~scanf("%d%d%d%d",&n,&m,&sx,&sy)){
solve();
puts(answer);
}
return ;
}
H
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e5+;
int n;
int a[M];
LL dp[][][];
LL solve(){
mt(dp,);
for(int i=;i<=;i++){
dp[][i][]=;
}
for(int i=;i<n;i++){
for(int j=;j<=;j++){
for(int k=;k<;k++){
if(dp[i][j][k]==) continue;
if(!k){
for(int x=;x<=;x++){
if(x>=j){
dp[i+][x][]+=dp[i][j][k];
}
else{
dp[i+][x][]+=dp[i][j][k];
}
}
continue;
}
for(int x=;x<=j;x++){
dp[i+][x][]+=dp[i][j][k];
}
}
}
}
LL sum=;
for(int j=;j<=;j++){
for(int k=;k<;k++){
sum+=dp[n-][j][k];
}
}
return sum;
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
while(~scanf("%d",&n)){
printf("%lld\n",solve());
}
return ;
}
F
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e2+;
int n,m;
struct P{
int k,t,qid,left;
}people[M];
struct Q{
int pid,need;
}node;
queue<Q> q[M];
void init(){
for(int i=;i<=m;i++){
while(!q[i].empty()) q[i].pop();
}
}
void solve(){
init();
int peopleID=;
for(int time=;;time++){
bool had=false;
for(int i=;i<=m;i++){
if(q[i].empty()) continue;
had=true;
q[i].front().need--;
if(q[i].front().need==){
people[q[i].front().pid].left=time;
q[i].pop();
}
}
if(!had&&peopleID>=n) break;
while(peopleID<n){
if(people[peopleID].k>time) break;
int id=,number=q[].size();
for(int i=;i<=m;i++){
if(number>q[i].size()){
number=q[i].size();
id=i;
}
}
people[peopleID].qid=id;
node.pid=peopleID;
node.need=people[peopleID].t;
q[id].push(node);
peopleID++;
}
}
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
while(~scanf("%d%d",&n,&m)){
for(int i=;i<n;i++){
scanf("%d%d",&people[i].k,&people[i].t);
}
solve();
for(int i=;i<n;i++){
printf("%d %d\n",people[i].qid,people[i].left);
}
}
return ;
}
D
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e3+;
int n,m;
char a[M][M];
char answer[M][M];
bool inside(int x,int y){
return x>=&&x<M&&y>=&&y<M;
}
void init(){
for(int i=;i<M;i++){
for(int j=;j<M;j++){
a[i][j]='';
}
}
for(int i=;i<M;i+=){
int sx=i;
int sy=;
while(inside(sx,sy)){
a[sx][sy]='#';
sx--;
sy++;
}
}
}
int get_sum(int sx,int sy){
int sum=;
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(a[sx+i][sy+j]=='#') sum++;
}
}
return sum;
}
void solve(){
int sx=,sy=;
int sum=get_sum(sx,sy);
int tx=,ty=;
int tsum=get_sum(tx,ty);
if(tsum<sum){
sum=tsum;
sx=tx;
sy=ty;
}
tx=,ty=;
tsum=get_sum(tx,ty);
if(tsum<sum){
sum=tsum;
sx=tx;
sy=ty;
}
for(int i=;i<n;i++){
for(int j=;j<m;j++){
answer[i][j]=a[sx+i][sy+j];
}
}
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
init();
while(~scanf("%d%d",&n,&m)){
solve();
for(int i=;i<n;i++){
for(int j=;j<m;j++){
putchar(answer[i][j]);
}
puts("");
}
}
return ;
}
J
//#define txtout
//#define debug
#include<bits/stdc++.h>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
const int M=1e4+;
int n,m,t;
int a[M];
struct E{
int u,v;
}e[M];
struct A{
vector<int> id;
LL t;
void init(){
t=;
id.clear();
}
}answer;
struct Q{
int need,id;
bool operator <(const Q &b) const {
return need>b.need;
}
}node;
priority_queue<Q> q;
vector<int> g[M];
int degree[M];
void init(){
answer.init();
for(int i=;i<=n;i++){
g[i].clear();
degree[i]=;
}
for(int i=;i<m;i++){
int u=e[i].u;
int v=e[i].v;
g[u].push_back(v);
degree[v]++;
}
}
void solve(){
init();
while(!q.empty()) q.pop();
for(int i=;i<=n;i++){
if(degree[i]==){
node.need=a[i];
node.id=i;
q.push(node);
}
}
LL time=;
while(!q.empty()){
node=q.top();
q.pop();
if(time+node.need>t) break;
time+=node.need;
int u=node.id;
answer.id.push_back(u);
for(int i=;i<g[u].size();i++){
int v=g[u][i];
degree[v]--;
if(degree[v]==){
node.id=v;
node.need=a[v];
q.push(node);
}
}
}
time=;
for(int i=;i<answer.id.size();i++){
int u=answer.id[i];
answer.t+=time+a[u];
time+=a[u];
}
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
while(~scanf("%d%d",&n,&t)){
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(int i=;i<m;i++){
scanf("%d%d",&e[i].u,&e[i].v);
}
solve();
printf("%d %I64d\n",answer.id.size(),answer.t);
for(int i=;i<answer.id.size();i++){
printf("%d%c",answer.id[i],i==answer.id.size()-?'\n':' ');
}
}
return ;
}
end