声明：本博菜，只做水。
题目网址：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3416比赛网址：
http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=319【Problem C】
水题，直接按题目意思写即可。
#include<stdio.h>
#define MAXN 210
int a[MAXN] , b[MAXN] ;
int bit( int x , int i)
{
return (x)&(1<<i) ? 1 : 0 ;
}
int f(int x ,int y){
int i , cnt = 0 ;
for(i = 0 ; i < 30 ; ++ i)
if(bit(x ,i) != bit(y , i)) ++ cnt ;
return cnt ;
}
int main(){
int n, m , test , ans , val , tr , i , j ;
scanf("%d" ,&test);
while(test -- ){
scanf("%d%d" , &n , &m);
for(i = 0 ; i < n ; ++ i) scanf("%d" , &a[i]);
for(i = 0 ; i < m ; ++ i) scanf("%d" , &b[i]);
for(j = 0 ; j < m ; ++ j){
val = 1000009 ; ans = 100 ;
for(i = 0 ; i < n ; ++ i)
{
tr = f(a[i] , b[j]);
if(tr < ans ){
ans = tr ; val = a[i] ;
}else if(tr == ans){
val = val < a[i] ? val : a[i] ;
}
}
printf("%d\n" , val);
}
}
return 0 ;
}【Problem E】
题目并不难：以相同的命令控制两个迷宫，求最少命令序列。
思路也容易想到，把两个球的坐标看成一个状态就行了，其余就是简单的广搜了。
问题是: 这题有很多小限制，例如最小字典序，节点的生成。非常考验编程的基本功。
可惜，我好像弄了2-3个小时。
#include<iostream>
#include<memory>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#define INF (1<<29)
using namespace std ;
struct node{
int x0 , y0 , x1 ,y1 ;
};
node start , end ;
char cmd[] = "DLRU" ;
int dx[] = {1 , 0 , 0 , -1} ;
int dy[] = {0 , -1 , 1 , 0} ;
// 数组t[]是为了便于找到方向信息在二进制中的位置
int t[] = {1 , 0 , 2 , 3 } ;
int bd0[6][6] , bd1[6][6];
int prev[1300] , mov[1300] ; // prev[i] 表示状态 i 的父亲节点 ，mov[i] 表示从状态 prev[i] 到 i 的操作。
// 将状态压缩成一个数字 ， 便于处理
inline int hash(node a){
return a.x0 * 216 + a.y0 * 36 + a.x1 * 6 + a.y1 ;
}
inline int bit(int x ,int i){
return x &(1<<i) ? 1 : 0 ;
}
inline int IsOut(int x ,int y){
return x<0||y<0||x>=6||y>=6;
}
inline int IsEnd(node a){
return hash(a) == hash(end);
}
//初始化找到 起始状态 和 终点状态
void init(){
int i , j ;
for(i = 0 ; i < 6 ; ++ i)
for(j = 0 ; j < 6 ; ++ j){
if(1 == bit(bd0[i][j], 5)) start.x0 = i , start.y0 = j ;
if(1 == bit(bd0[i][j], 6)) end.x0 = i , end.y0 = j ;
if(1 == bit(bd1[i][j], 5)) start.x1 = i , start.y1 = j ;
if(1 == bit(bd1[i][j], 6)) end.x1 = i , end.y1 = j ;
}
}
//构造字典序最小的解
void MakeSolution(int val){
if(prev[val] != INF){
MakeSolution(prev[val]) ;
printf("%c" , cmd[mov[val]]);
}
}
void Run(){
int i , cx0 , cy0 , cx1 , cy1 ,nx0 ,ny0 ,nx1 , ny1 , val ;
node cur , nxt ;
queue<node> Q ;
init();
if(IsEnd(start)) return ;
memset(prev , -1 ,sizeof(prev));
prev[ hash(start) ] = INF ;
Q.push(start);
while(!Q.empty()){
cur = Q.front() ; Q.pop();
cx0 = cur.x0 , cy0 = cur.y0 , cx1 = cur.x1 , cy1 = cur.y1 ;
// 由于要求构造的解满足字典序最小，所以应该选择以 < D , L , R , U>这种顺序拓展。
for(i = 0 ; i < 4 ; ++ i)
if(!bit(bd0[cx0][cy0],t[i])||!bit(bd1[cx1][cy1] ,t[i])){
nx0 = cx0 + dx[i] , ny0 = cy0 + dy[i] ;
nx1 = cx1 + dx[i] , ny1 = cy1 + dy[i] ;
//生成 next 这个儿子节点 ， 碰壁时则不动
if(!bit(bd0[cx0][cy0] , t[i])){
nxt.x0 = nx0 , nxt.y0 = ny0 ;
} else {
nxt.x0 = cx0 , nxt.y0 = cy0 ;
}
if(!bit(bd1[cx1][cy1] , t[i])){
nxt.x1 = nx1 , nxt.y1 = ny1 ;
}else{
nxt.x1 = cx1 , nxt.y1 = cy1 ;
}
if(IsOut(nxt.x0,nxt.y0)||IsOut(nxt.x1,nxt.y1)) continue ; // 判断出界
if(!bit(bd0[nxt.x0][nxt.y0],4)||!bit(bd1[nxt.x1][nxt.y1],4)) continue ; // 判断是否为洞
if(prev[val = hash(nxt)] != -1) continue ; // 判断是否重复
prev[val] = hash(cur) ; mov[val] = i ;
//终点状态
if(IsEnd(nxt)){
MakeSolution(val); return ;
}
Q.push(nxt);
}
}
printf("-1");
}
int main(){
int i ,j , tst ;
scanf("%d" , &tst);
--tst ;
for(i = 0 ; i < 6 ; ++ i)
for(j = 0 ; j < 6 ; ++ j)
scanf("%d" ,&bd0[i][j]);
while(tst--){
for(i = 0 ; i < 6 ; ++ i)
for(j = 0 ; j < 6 ; ++ j)
scanf("%d" ,&bd1[i][j]);
Run();
printf("\n") ;
for(i = 0 ; i < 6 ; ++ i)
for(j = 0 ; j < 6 ; ++ j)
bd0[i][j] = bd1[i][j] ;
}
return 0;
}
【Problem F】
定义：
F(x) = max( Si(x) ) , 其中 Si(x) = ai*x^2 + bi*x + ci . 这里 0<=ai 。
稍微观察一下，即可发现F(x)是一个纯单调函数或者单峰函数。速度三分法水.....
只是这里特别注意精度问题，经测试，当 eps > 1e-9 时，果断WA 。
#include<stdio.h>
#define MAXN 10005
#define EPS (1e-10)
#define INF (1e100)
typedef struct{
double a ,b ,c ;
}node;
node e[MAXN] ;
int n ;
double f(node t , double x){
return t.a * x * x + t.b * x + t.c ;
}
int sgn(double x){
return (x>EPS) - (x<-EPS) ;
}
double can(double x){
double maxval = -INF , tr ;
int i ;
for(i = 0 ; i <n ; ++i)
{
tr = f(e[i] , x);
if(tr > maxval)
maxval = tr ;
}
return maxval ;
}
double Min(double x, double y){
return x < y ? x :y ;
}
double Run(){
double ans , t1 , t2 , t3 ,t4 ;
int i ;
t1 = 0.0 ; t4 = 1000.0 ;
for(i = 0 ; i < 100 ; ++i){
t2 = (t4 - t1)/3.0 + t1 ;
t3 = (t4 - t1)/1.5 + t1 ;
if(can(t2) < can(t3))
t4 = t3 ;
else
t1 = t2 ;
if(!sgn(t1-t4)) break ;
}
return can(t1) ;
}
int main(){
int test ,i;
int a , b , c;
scanf("%d" , &test);
while(test -- ){
scanf("%d",&n);
for(i = 0 ; i < n ; ++i){
scanf("%d%d%d" ,&a ,&b , &c) ;
e[i].a = (double)a ;
e[i].b = (double)b;
e[i].c = (double)c;
}
printf("%0.4lf\n" ,Run());
}
return 0;
}
【Problem G】
常用思路： 2_SAT + 二分。
这里 2_SAT模型中的 <a , ~a> 对应于 x[i] 取 0 或者 1 。
互斥条件是 ： x[a[dep]] + x[b[dep]] == c[dep] 。
图中的点数为 2*n , 边数最多为 m 。 复杂度 O(m*log(m))。
对答案进行二分即可。
#include<iostream>
#include<stdio.h>
#include<cstring>
#define MAXN 405
#define MAXM 10005
using namespace std ;
bool gh[MAXN][MAXN] ;
int N , Ecnt , a[MAXM] , b[MAXM] ,c[MAXM];
void build(int MaxDepth){
int i , j , dep , x, y;
for(i = 0 ; i < 2*N ; ++ i)
for(j = 0 ; j < 2*N ; ++ j)
gh[i][j] = 0 ;
for(dep = 0 ; dep < MaxDepth ; ++ dep){
x = a[dep] , y = b[dep] ;
if(0 + 0 == c[dep]) gh[2*x][2*y+1] = gh[2*y][2*x+1] = 1 ;
if(0 + 1 == c[dep]) gh[2*x][2*y] = gh[2*y+1][2*x+1] = 1 ;
if(1 + 0 == c[dep]) gh[2*x+1][2*y+1] = gh[2*y][2*x] = 1 ;
if(1 + 1 == c[dep]) gh[2*x+1][2*y] = gh[2*y+1][2*x] = 1 ;
}
}
int bcnt , idx ,top , stk[MAXN] ,instk[MAXN] , dfn[MAXN] , low[MAXN] ,bel[MAXN] ;
void Tarjan(int x){
int y ;
low[x] = dfn[x] = ++idx ;
instk[x] = 1 ; stk[top++] = x ;
for(y = 0 ; y <2*N ; ++y)
if(gh[x][y]){
if(dfn[y] == -1){
Tarjan(y);
low[x] = min(low[x] , low[y]);
}else if(instk[y]){
low[x] = min(low[x] , dfn[y]);
}
}
if(low[x] == dfn[x]){
++bcnt ;
do{
y = stk[--top] ; instk[y] = 0 ; bel[y] = bcnt ;
}while(y!=x);
}
}
bool check(int mid){
int i ;
build(mid);
bcnt = idx = top = 0 ;
for(i = 0 ; i < 2*N; ++i){
dfn[i] = -1 , instk[i] = 0 ;
}
for(i = 0 ; i < 2*N ; ++ i)
if(dfn[i] == -1) Tarjan(i);
for(i = 0 ; i < N ; ++ i)
if(bel[2*i] == bel[2*i+1]) return false ;
return true;
}
int main(){
int test , i , j , x, y ;
scanf("%d" ,&test);
while(test--){
scanf("%d%d" ,&N ,&Ecnt);
for(i = 0 ; i < Ecnt ; ++ i)
scanf("%d%d%d" , &a[i] ,&b[i] , &c[i]);
int l , r , mid , ans ;
l = ans = 1 , r = Ecnt ;
while(l <= r){
mid = (l + r ) / 2 ;
if(check(mid)){
ans = mid , l = mid + 1 ;
}else{
r = mid - 1 ;
}
}
printf("%d\n" ,ans);
}
return 0 ;
}【Problem J】
最大费用最大流 or 最佳匹配算法 ( KM 算法)。
设标准答案串为 T ， 学生答案串为S 。
算法设计:
(1). 分别统计<t,s>的对数为f(t,s)，其中 t 属于 T , s 属于 S 。
(2). X = {A,B,..,Z} , Y = {A,B,..,Z}.
以 X 集和 Y 集建一个二分图。
对每一对<t,s> 从 X 中的字母 t 连一条边至 Y 集中的s , 边权为 f(t,s) 。
(3). 求二分图的最优匹配 ( KM算法 or 最大费用最大流 ) 即答案。
#include<iostream>
#include<stdio.h>
#include<queue>
#define INF 1<<29
#define MAXN 60
#define MAXS 10005
using namespace std;
typedef struct{
int y , c , cost , next ;
}node ;
node e[MAXN*MAXN] ;
int es , hd[MAXN] , S , T,Vcnt ;
int cnt[MAXN][MAXN];
int TT[MAXS] , SS[MAXS] ;
int dist[MAXN] ,vis[MAXN] ,prev[MAXN] , pos[MAXN] ;
void ins(int x , int y ,int c ,int cost){
e[es].y = y , e[es].c = c , e[es].cost = cost , e[es].next = hd[x] , hd[x] = es ++;
e[es].y = x , e[es].c = 0 , e[es].cost = -cost ,e[es].next = hd[y] , hd[y] = es ++;
}
void Build(){
int i , j , k ;
es = 0 ; S = 53 ; T = 54 ; Vcnt = 54 ;
for(i = 1 ; i <= Vcnt ; ++ i) hd[i] = -1 ;
for(i = 1 ; i <= 26 ; ++i)
for(j = 1 ; j<=26 ; ++j)
if(cnt[i][j]!=0)
ins(i , 26 + j , 1 , -cnt[i][j]);
for(i = 1 ; i <= 26 ; ++i){
ins(S , i , 1 , 0 );
ins(26+i ,T , 1 , 0);
}
}
int Spfa(){
int i , j , k , x ,y ;
queue<int> Q ;
for(i = 1 ; i<=Vcnt ; ++ i) {
prev[i] = -1 , vis[i] = 0 , dist[i] = INF;
}
Q.push(S) ; dist[S] = 0 ; vis[S] = 1 ;
while(!Q.empty()){
x = Q.front() , Q.pop() ; vis[x] = 0 ;
for(i = hd[x] ; i!=-1 ; i=e[i].next){
y = e[i].y ;
if(e[i].c && dist[y] > dist[x] + e[i].cost){
dist[y] = dist[x] + e[i].cost ;
prev[y] = x ; pos[y] = i ;
if(vis[y] == 0){
vis[y] = 1 ; Q.push(y);
}
}
}
}
return prev[T] != -1 ;
}
int MinCost(){
int res = 0 , del , i , j ,k , u, v;
while(Spfa()){
del = INF ;
for(u = T ; u!=S ; u = prev[u]) del = min(del , e[pos[u]].c);
for(u = T ; u!=S ; u = prev[u])
e[pos[u]].c -= del , e[pos[u]^1].c += del ;
res += del * dist[T] ;
}
return res ;
}
int main(){
int cs , test , N ,K , M ,i ,j , ans;
char ss[3];
scanf("%d" ,&test);
while(test--){
scanf("%d%d%d" , &N , &K ,&M);
for(i = 0 ; i < N ; ++ i){
scanf("%s" , ss);
TT[i] = ss[0] - 'A' + 1;
}
for(cs = 0 ; cs < M ; ++ cs){
for(i = 0 ; i < N ; ++ i)
scanf("%s" ,ss) , SS[i] = ss[0]-'A' + 1 ;
for(i = 1 ; i <= Vcnt; ++ i)
for(j = 1 ; j <= Vcnt ; ++ j)
cnt[i][j] = 0 ;
for(i = 0 ; i < N ; ++ i)
++ cnt[TT[i]][SS[i]] ;
Build();
ans = -MinCost();
printf("%0.4lf\n" , (double)ans/(double)N);
}
}
//while(getchar());
return 0 ;
}