2014ACM/ICPC亚洲区北京站现场赛(HDU 5111,5115,5119,5120,5122)
HDU 5112
水题，注意取绝对值和浮点数
#include
#include
#include
using namespace std;
struct Point {int t;int x;
};
int cmp(Point a,Point b) {return a.tmax) max=v;}printf("Case #%d: %.2lf\n",cas++,max);}
} HDU 5122
这个题卡了好久，刚开始思路就错了。以为是之前想过的冒泡外层循环的次数，直接求最大逆序数。WA了4个小时。最后才发现题意就理解错了。
树状数组，每次移动最大数字，那它位置后的数字都前移一位。每次看以后每次在判断次数。
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define maxn 1100000
using namespace std;
int n;
struct Node
{int val;int pos;
}node[maxn];
int a[maxn];
void update(int pos,int x)
{while(pos<=n){a[pos]+=x,pos+=lowbit(pos);}
}
int getsum(int pos)
{int res=0;while(pos>0){res+=a[pos],pos-=lowbit(pos);}return res;
}
bool cmp(const Node& a, const Node& b)
{return a.val > b.val;
}
int main()
{int T;scanf("%d",&T);int cont=0;while (T--){scanf("%d",&n);cont++;for (int i = 1; i <= n; ++i){scanf("%d", &node[i].val);node[i].pos = i;}sort(node + 1, node + n + 1, cmp);memset(a,0,sizeof(a));int ans=0;for(int i=1;i<=n;i++){int t=getsum(node[i].pos);if(node[i].pos-t!=node[i].val)ans++,update(node[i].pos,1);}printf("Case #%d: %d\n",cont, ans);}return 0;
} HDU 5115
裸区间DP
刚开始用双向链表写了个贪心策略的。看起来真优美啊，WA
#include
#include
#include
#include
#define inf 0x3f3f3f3f
#define maxn 210
typedef long long ll;
using namespace std;
int N,M,T;
int V[maxn];
int pre[maxn],next[maxn];
struct P
{int pos,val,give;
}p[maxn];
bool cmp(const struct P &a,const struct P &b)
{if(a.give==b.give)return V[ pre[a.pos] ]+V[ next[a.pos] ] < V[ pre[b.pos]]+V[pre[b.pos]];return a.give>b.give;
}
int main()
{scanf("%d",&T);int cnt=0;while (T--){scanf("%d",&N);ll ans=0;for(int i=1;i<=N;i++)scanf("%d",&p[i].val),p[i].pos=i;for(int i=1;i<=N;i++)scanf("%d",&p[i].give),V[i]=p[i].give;V[0]=V[N+1]=0;p[N+1].pos=N+1;p[N+1].val=p[N+1].give=0;p[0].pos=p[0].val=p[0].give=0;for(int i=1;i<=N;i++)next[i]=i+1,pre[i]=i-1;sort(p+1,p+N+1,cmp);///memset(dp,0,sizeof(dp));for(int i=1;i<=N;i++){ans+=V[ pre[ p[i].pos ] ] +V[ next[ p[i].pos ] ] +p[i].val;next[ pre[ p[i].pos ] ]=next[ p[i].pos ];pre[ next[ p[i].pos ] ]=pre[ p[i].pos ];sort(p+i+1,p+N+1,cmp);}printf("Case #%d: %I64d\n",++cnt, ans);}return 0;
} AC:
#include
using namespace std;int main() {int T;cin >> T;for (int cas = 1; cas <= T; cas++) {int N;cin >> N;int a[202], b[202];int dp[202][202];for (int i = 1; i <= N; i++) {cin >> a[i];}for (int i = 1; i <= N; i++) {cin >> b[i];}b[0] = b[N + 1] = 0;for (int i = 1; i <= N; i++) {dp[i][i] = a[i] + b[i - 1] + b[i + 1];}for (int i = 1; i <= N ; i++) {for (int j = 1; j + i <= N ; j++) {dp[j][j + i] = -1;for (int k = j; k <= j + i; k++) {int temp;if( k==j )temp = dp[k+1][j+i] + a[k] + b[j+i+1] + b[j-1];else if( k==i+j )temp = dp[j][k-1] + a[k] + b[j-1] + b[j+i+1];else temp = dp[j][k-1] + dp[k+1][j + i] + a[k] + b[j-1] + b[j + i + 1];if (dp[j][j + i] == -1 || temp < dp[j][j + i] ) {dp[j][j + i] = temp;}}}}cout << "Case #" << cas << ": " << dp[1][N] << endl;}return 0;
} HDU 5119
裸背包，放或不放的两种情况产生结果的转移。因为数字是小于1<<20，所以遍历到此即可。
注意2^40，要用Long long 因为这个卡了1次。
#include
#include
#include
using namespace std;int N,M,T;
long long dp[2][1<<20];
int in[50];
int main()
{scanf("%d",&T);int cnt=0;while(T--){scanf("%d%d",&N,&M);for(int i=1;i<=N;i++)scanf("%d",in+i);memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<=N;i++)for(int j=0;j<(1<<20);j++)dp[i%2][j^in[i]]=dp[(i-1)%2][j]+dp[(i-1)%2][j^in[i]];long long ans=0;for(int i=M;i<(1<<20);i++)ans+=dp[N%2][i];printf("Case #%d: %I64d\n",++cnt,ans);}
}
计算几何模板题，同学备好模板哦
#include
#include
const double eps = 1e-8;
const double PI = acos(-1.0);
double min(double a,double b) {return a 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！