首页 > 代码库 > 付忠庆的赛后小笔记 ---Qtech交流赛

付忠庆的赛后小笔记 ---Qtech交流赛

刚刚去山东理工大学的OJ看了一下问题没有公开。。。不过幸好大部分题可以再其他网站上找到 XD

A

四子棋 --ACM Mid-Central 1999 // 对抗搜索(要求剪枝, 容易超时)    http://poj.org/problem?id=1568

这个题是我们比赛过程中尝试的最后一道题,但是写到一半就断电了.....(就算不断电我也没有信心能A过去).....

其实在赛场和剑神坤队讨论的算法就没问题,写一个简单的AI(就是题解所说的对抗搜索)庆幸的是我高中接触过极其相似的----bingo,大概就是优先选择‘x‘较多的排或列或对角线注意也要关注较多的‘O‘排或列或对角线,关于剪枝就是每排每列有不同的妻子就可以终止(可以想一想为什么)

就是需要些大量的代码而且保持脑子不绕  这是一项技能。。。

这是标准程序:

  1 // 1999 ACM Mid-Central Regional Programming Contest  2 // Problem A: Find the Winning Move  3 // by Dr. Eric Shade, Computer Science Department, SMSU  4   5 /**  6  * modified by neko13  7  */  8   9 import java.io.*; 10 import java.util.*; 11 import static java.lang.System.*; 12  13  14 public class Main { 15     static final char SPACE = ‘.‘; 16     static Scanner cin = new Scanner(in); 17     static char[] board; 18      19     public static void main(String args[]) throws IOException { 20         // ACMIO in = new ACMIO("win.in"); 21         // PrintWriter out = new PrintWriter(new FileWriter("win.out")); 22          23         for (String cmd = cin.nextLine(); cmd.equals("?"); cmd = cin.nextLine()) { 24             String a = cin.nextLine(); 25             String b = cin.nextLine(); 26             String c = cin.nextLine(); 27             String d = cin.nextLine(); 28             String e = a+b+c+d; 29             board = e.toCharArray(); 30  31             // show(); 32  33             int k = findForcedWin(); 34  35             if (k >= 0) 36                 out.println("(" + k/4 + "," + k%4 + ")"); 37             else 38                 out.println("#####"); 39         } 40  41         out.close(); 42     } 43  44  45     public static int findForcedWin() { 46         for (int i = 0; i < 16; ++i) 47             if (board[i] == SPACE && xForcedWinPlaying(i)) 48                 return i; 49  50         return -1;                 51     } 52  53      54     public static boolean xForcedWinPlaying(int i) { 55         board[i] = ‘x‘; 56          57         if (! isWin(i, ‘x‘)) { 58             for (int j = 0; j < 16; ++j) { 59                 if (board[j] == SPACE && ! oForcedLossPlaying(j)) { 60                     board[i] = SPACE; 61                     return false; 62                 } 63             } 64         } 65  66         board[i] = SPACE; 67         return true; 68     } 69  70      71     public static boolean oForcedLossPlaying(int j) { 72         board[j] = ‘o‘; 73  74         if (! isWin(j, ‘o‘)) { 75             for (int i = 0; i < 16; ++i) { 76                 if (board[i] == SPACE && xForcedWinPlaying(i)) { 77                     board[j] = SPACE; 78                     return true; 79                 } 80             } 81         } 82  83         board[j] = SPACE; 84         return false; 85     } 86  87  88     public static boolean isWin(int i, char player) { 89         int r = 4 * (i / 4); 90         int c = i % 4; 91          92         return (board[r    ] == player && board[r + 1] == player && 93                 board[r + 2] == player && board[r + 3] == player) 94             || (board[c    ] == player && board[c + 4] == player && 95                 board[c + 8] == player && board[c +12] == player) 96             || (board[ 0] == player && board[ 5] == player && 97                 board[10] == player && board[15] == player) 98             || (board[ 3] == player && board[ 6] == player && 99                 board[ 9] == player && board[12] == player);100     }101 102     103     public static void show() {104         for (int i = 0; i < 16; ++i) {105             System.out.print(board[i]);106             if (i%4 == 3) System.out.println();107         }108     }109 }

B

幸运数

如果A,B是幸运数那么A+B+2也是幸运数 现在给你A B C已知A B是幸运数请问C是不是幸运数

//以下是原题解 我老是感觉那里错了......难道是我的问题?

幸运数:c=a+b+2可以化为(c+2)=(a+2)+(b+2),即c=a+b;所以任何一个幸运数都是由最初的两个幸运数所组成的,即c=x*a+y*b。

//另外刚开始我也理解错了,(其实都怪领导!)以为简单判断a+b+2==c就行了 但是忘记了c==a+a+2  c==b+b+2   c==(a+b+2)+a+2    c==(a+b+2)+b+2.........一系列的情况

我的题解

我们就先把a,b叫基本元, 不难看出c-2是由两个基本元组成的  c-4是三个  c-6是四个。。。。 所以我们从c-2开始 到 min(a,b)结束(不包括) 遍历一遍,然后在每次遍历中我们在判断是否可以写成 nx+my形式就可以了

大概是这样:c-2*p=nx+my (n+m=p)

代码嘛。。。

void fun1()

{

if (有时间) 补上;

}

fun1();

//更新 ----这是标程 和我的思想不一样。。。

 1 #include<iostream> 2  3 using namespace std; 4  5 int gcd(int x,int y) 6 { 7     if(!x || !y) return x>y?x:y; 8     for(int t;t=x%y;x=y,y=t); 9     return y;10 }11 12 int main()13 {14     int t,a,b,c;15     cin>>t;16     while(t--)17     {18         cin>>a>>b>>c;19         a+=2;b+=2;c+=2;20         int g=a*b/gcd(a,b);21         int n=c/a,m=c%a;22         while(m%b)23         {24             if(n==0) break;25             n--;26             g-=a;27             if(g==0) break;28             m+=a;29         }30         if(m%b) cout<<"No."<<endl;31         else cout<<"Yes."<<endl;32     }33     return 0;34 }

 

C

大水题我就不说了

遍历一遍找到最大最小下标 然后cout

D

给了 r1 r2 r3 求三角形ABC面积

呵呵,数学题我还是....贴文献吧

http://wenku.baidu.com/link?url=Tly1I1zFpQ9pFBRZ4kDHM9xfiBlSyuvExgdakBsk4oAw_KLxCZSKX05j4UP16P7kqd8-A6ZLHJ06tRKx9eLN2ufhsM7NQ347NC_ZiIWgna3

三角形:用向量法求出三个圆的圆心,然后即可求出三条切线。

#include<iostream>#include<cmath>#include<cstdio>#define sqr(a) ((a)*(a))using namespace std;const double eps=1e-8;const double pi=2.0*asin(1.0);double getangle(double a,double b,double c){    return acos((sqr(a)+sqr(b)-sqr(c))/(2*a*b));}double getangle(double a,double b){    return asin((a-b)/(a+b));}typedef struct point{    double x,y;    point(double xx=0,double yy=0):x(xx),y(yy){}}vector;point operator + (point a,vector b){    return point(a.x+b.x,a.y+b.y);}vector operator - (point a,point b){    return vector(a.x-b.x,a.y-b.y);}vector operator * (vector a,double b){    return vector(a.x*b,a.y*b);}double dot(vector a,vector b){    return a.x*b.x+a.y*b.y;}double cross(vector a,vector b){    return a.x*b.y-a.y*b.x;}vector rotate(vector a,double b){    double s=sin(b),c=cos(b);    return vector(a.x*c-a.y*s,a.x*s+a.y*c);}double len(vector a){    return sqrt(sqr(a.x)+sqr(a.y));}vector resize(vector a,double b){    b/=len(a);    return vector(a.x*b,a.y*b);}point inter(point a,vector v,point c,vector w){    vector u=a-c;    double t=cross(w,u)/cross(v,w);    return a+v*t;}int main(){    double r1,r2,r3;    int t;    cin>>t;    for(int i=1;i<=t;i++)    {        cin>>r1>>r2>>r3;        point c1,c2,c3;        c1=point(0,r1);        c2=point(sqrt(sqr(r1+r2)-sqr(r1-r2)),r2);        double a=r1+r2,b=r2+r3,c=r3+r1;        c3=inter(c1,rotate(c2-c1,getangle(c,a,b)),c2,rotate(c1-c2,-getangle(a,b,c)));        vector v1=vector(1,0),v2=vector(rotate(c3-c2,getangle(r2,r3))),v3=vector(rotate(c1-c3,getangle(r3,r1)));        if(cross(v1,v2)<eps || cross(v2,v3)<eps || cross(v3,v1)<eps)        {            printf("No Solution!\n");continue;        }        point p1=point(0,0),p2=c2+resize(rotate(v2,-pi/2),r2),p3=c3+resize(rotate(v3,-pi/2),r3);        point pa=inter(p1,v1,p3,v3),pb=inter(p2,v2,p1,v1),pc=inter(p3,v3,p2,v2);        double s=cross(pb-pa,pc-pa)/2;        printf("%.3lf\n",s);    }}

E

中心点

 给出若干个点p1 p2...pn的坐标 有一个点

这个点到p1p2 ...pn距离和最小,求最小值  

原题

http://poj.org/problem?id=2420

// 模拟退火求费马点(随机算法, 要求精度足够)
和我的想法完全不同....我就不贴我的代码了 完全错误...

ps:费马点就是在把这个题目的若干个点改为3个点,本题为费马点的推广....

 1 #include <iostream> 2 #include <cmath> 3 #include <iomanip> 4 using namespace std; 5  6 double x[100], y[100]; 7 int N; 8  9 double test(double xx, double yy) {10    double total = 0;11    for (int i=0;i<N;i++)12       total+=sqrt(pow(x[i]-xx,2)+pow(y[i]-yy,2));13    return total;14 }15 16 int main()17 {18    double xx,yy;19    double delta;20    cin>>N;21    for(int i=0;i<N;i++)22     cin>>x[i]>>y[i];23    xx = 5000;24    yy = 5000;25    for (delta=5000;delta>0.1;delta*=0.9) {26       if (test(xx,yy+delta) < test(xx,yy)) yy+=delta;27       if (test(xx,yy-delta) < test(xx,yy)) yy-=delta;28       if (test(xx+delta,yy) < test(xx,yy)) xx+=delta;29       if (test(xx-delta,yy) < test(xx,yy)) xx-=delta;30    }31    cout<<setiosflags(ios::fixed);32    cout<<setprecision(0)<<test(xx,yy)<<endl;33    return 0;34 }

F

博弈论

只要判断n==2^k-1 就行了 。。。。有一(大)部分头文件是无用的

#include <set>#include <map>#include <list>#include <cmath>#include <ctime>#include <deque>#include <queue>#include <stack>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <cassert>#include <cstdlib>#include <cstring>#include <sstream>#include <iostream>#include <algorithm>using namespace std;int grundy( int n ) {    if( n == 1 ) return 0;    if( n & 1 ) return grundy( n/2 );    return n/2;}int main() {    int n;    while( scanf("%d", &n) == 1 && n ) {        printf("%s\n", grundy(n) ? "Alice" : "Bob");    }    return 0;}

G

令人眼花缭乱的Dp //有时间再消化吧!

还是要吐槽一句考虑Dp算法的时候就怕想太多!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!其实根本没必要想那么多!!!

 1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <ctime> 6 #include <deque> 7 #include <queue> 8 #include <stack> 9 #include <cctype>10 #include <cstdio>11 #include <string>12 #include <vector>13 #include <cassert>14 #include <cstdlib>15 #include <cstring>16 #include <sstream>17 #include <iostream>18 #include <algorithm>19 20 using namespace std;21 22 const double inf = 1e50;23 const int NN = 10005;24 25 int n, P;26 27 struct info {28     int p1, p2, t1, t2, w1, w2;29 }A[NN];30 31 double dp[2][101][7];32 33 int main() {34 35     double cl = clock();36     while( scanf("%d %d", &n, &P) == 2 && n ) {37         for( int i = 1; i <= n; i++ ) scanf("%d %d %d %d %d %d", &A[i].p1, &A[i].p2, &A[i].t1, &A[i].t2, &A[i].w1, &A[i].w2);38 39         for( int i = 1; i <= 100; i++ ) for( int j = 0; j <= 6; j++ ) dp[0][i][j] = inf;40         dp[0][P][0] = 0;41         int cur = 1, prev = 0;42         for( int k = 1; k <= n; k++ ) {43             for( int i = 1; i <= 100; i++ ) for( int j = 0; j <= 6; j++ ) dp[cur][i][j] = inf;44 45             for( int i = 1; i <= 100; i++ ) for( int j = 0; j <= 6; j++ ) if( dp[prev][i][j] < inf && i >= A[k].p1 ) {46                 int i1 = i + A[k].w1;47                 int j1 = j + A[k].w2;48 49                 if( i1 * (1 << j1) >= 100 ) i1 = 100, j1 = 0;50 51                 double r;52 53                 if( i >= A[k].p2 ) r = A[k].t2;54                 else r = A[k].t2 + (A[k].p2 - i + 0.) * ( A[k].t1 - A[k].t2 ) / (A[k].p2 - A[k].p1);55 56                 dp[cur][i1][j1] = min( dp[cur][i1][j1], r + dp[prev][i][j] );57 58             }59 60             for( int j = 6; j > 0; j-- ) for( int i = 1; i <= 100; i++ ) if( dp[cur][i][j] < inf ) {61                 int i1 = min( i * 2, 100 );62                 int j1 = j - 1;63                 dp[cur][i1][j1] = min( dp[cur][i1][j1], dp[cur][i][j] );64             }65 66             swap( cur, prev );67         }68         double res = inf;69         for( int j = 6; j >= 0; j-- ) for( int i = 1; i <= 100; i++ ) res = min( res, dp[prev][i][j] );70         if(res > inf/2) printf("Impossible\n");71         else printf("%.2lf\n", res + 1e-11);72     }73 74     cl = clock() - cl;75     fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC);76 77     return 0;78 }

H(H,I,J题号和对应题目我给忘了,可能顺序不对)

有一个是给出图形计算面积的

这道题很简单啊 hahahahaha~

1每一行分解为一个小图形  最后加起来

对于每一行

     2 刚开始如果出现‘.‘是不计入的一直到‘/‘或‘\‘出现 才计入,然而通过这个发现‘./.\./.\.’累计有奇数个/或\就计入 否则不计入

     3 ‘.‘代表1 ‘/‘‘\‘代表1/2不过可以保证‘/‘‘\‘出现次数是偶数

这样就解出来了

fun1();

I

还有一个数论的问题

1^k+2^k+...+n^k  mod 1000000007(1和7之间几个0忘记了,在7~10个范围中)

只用快速幂TLE,原因 : n<10000000000;

当然不应该傻乎乎的加啦  有通项公式的说!

这个通项公式是一个非常特别的
公式为
1^k+2^k+...+n^k=((n+1+p)^(k+1)-p^(k+1))/(k+1)
我们先要求一个数字p,p满足以下规则
(1+p)^(k+1)-p^(k+1)=0这个里面首先要展开,展开后对于p,p^2 p^3等,我们要当成一个整体对待,比如
k=1的时候
(1+p)^2-p^2=0
1+2p=0 p=-1/2
k=2的时候
(1+p)^3-p^3=0
1+3p+3p^2=0
其中p=-1/2,代入
p^2=1/6
也就是说,p p^2 p^3这些数字之间相对独立
我们来看看k=1的时候我们计算的通项
1+2+..+n=((n+1+p)^2-p^2)/2=((n+1)^2+2(n+1)p)/2
p=-1/2代入
=((n+1)^2-(n+1))/2=n(n+1)/2

我们来看k=2的时候
p=-1/2 p^2=1/6前面已经计算了,不再重复
1^2+2^2+....+n^2=((n+1+p)^3-n^3)/3
=((n+1)^3+3(n+1)^2*p+3(n+1)p^2)3
代入p,p^2
=((n+1)^3-3(n+1)^2/2+3*(n+1)/6)/3
=(n+1)((2(n+1)^2-3(n+1)+1)/6
=(n+1)((2n^2+4n+2-3n-3+1)/6
=(n+1)(2n^2+n)/6=n(n+1)(2n+1)/6

J

还有一个是一个简单题

素数间隙

给一个数  如果这个数是素数输出0 否则输出  比这个数大的素数中最小的数a1  和 比这个小的素数中最大的数a2  之差 a1-a2

两种做法

我用的打表+暴力, 或者线性素数筛+二分

http://poj.org/problem?id=3518

代码嘛。。。

fun1();

 

 

。。。。。结束了

while(1)

RP++;

 

付忠庆的赛后小笔记 ---Qtech交流赛