链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=61581#overview
描述：很老的CF题,题不错,拿来训练正好。做的时候刚做完BC，还时不时去hdu看看有木有judge结束，题有木有挂掉，脑子有点糊涂，当时过了三题（按自己平时做CF的顺序作的）。代码写得也很繁琐（就记得B题T成狗，最后在群里的提醒下过了...)。当然现在脑子也是糊涂，打完北京赛区然后就要连续考试三门我也是醉了。要不是马上比赛就要关了赛后AK的时间估计还要再往后拖他个几天...不管是不是退役这种比赛确实是做一场少一场了，写个解题报告留个念吧。
题解：
题意：给出天数和总共要学习的小时数，并且给出每天能学习的最长时间和最短时间，问能不能正常完成任务。
思路：直接找到上限下限看在不在其中即可。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const LL MOD = 1000000007 ;
int Min[35],Max[35];
bool vis[35];
int n[35];
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
int a,b;
scanf("%d%d",&a,&b);
int Lim_min=0,Lim_max=0;
for(int i=1;i<=a;i++)
{
scanf("%d%d",&Min[i],&Max[i]);
Lim_min+=Min[i];
Lim_max+=Max[i];
}
if(b>Lim_max||b<Lim_min)
puts("NO");
else
{
puts("YES");
for(int i =1;i<=a;i++)
{
//cout<<n[i]<<Min[i];
n[i]=Min[i];
//cout<<n[i]<<Min[i]<<endl;
}
int sub=b-Lim_min;
for(int i=1;i<=a;i++)
{
if(sub==0)
break;
else
{
//cout<<i<<" "<<Max[i]<<" "<<Min[i]<<" "<<n[i]<<endl;
//cout<<sub<<endl;
n[i]+=min(Max[i]-n[i],sub);
sub-=n[i]-Min[i];
}
}
for(int i=1;i<=a;i++)
if(i!=1)
printf(" %d",n[i]);
else printf("%d",n[i]);
printf("\n");
}
return 0;
}
题意：给出一个n*n的矩阵（每个点的值都是非负数），初始数值是1，从矩阵左上角走到矩阵右下角走出一条路径，把沿途的所有数都乘到自己身上，问最后后缀有多少个0。
思路：简单DP，从左上向右下推两次，第一次找到可以得到的2的最少数，第二次找到可以得到的5的最少数，两次推得的比较少的数量就是后缀0的最少数。特殊情况是矩阵中存在0的情况，如果所得的最优路径上得到的后缀0数超过1个，那么就取经过0的路径，这样后缀0就只有1个。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int M[1005][1005];
int a[1005][1005][2];
int dp2[1005][1005],dp5[1005][1005];
int from2[1005][1005],from5[1005][1005];//1是上，2是左
int main()
{
#ifdef LOCAL
freopen("out.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
#endif
int t;
scanf("%d",&t);
bool flag = 0;
int tox = -1, toy= -1;
for(int i=0; i<t; i++)
for(int j=0; j<t; j++)
{
scanf("%d",&M[i][j]);
if(M[i][j]==0)
{
tox=i;
toy=j;
flag = 1;
}
int ttt=M[i][j];
if(ttt!=0)
{
while(ttt%2==0&&ttt!=0)
{
a[i][j][0]++;
ttt/=2;
}
ttt=M[i][j];
while(ttt%5==0&&&ttt!=0)
{
a[i][j][1]++;
ttt/=5;
}
}
if(i==0&&j==0)
{
dp2[0][0]=a[0][0][0];
dp5[0][0]=a[0][0][1];
}
else
{
if(i==0)
{
dp2[i][j]=dp2[i][j-1]+a[i][j][0];
from2[i][j]=2;
}
else if(j==0)
{
dp2[i][j]=dp2[i-1][j]+a[i][j][0];
from2[i][j]=1;
}
else
{
if(dp2[i][j-1]<dp2[i-1][j])
{
dp2[i][j]=dp2[i][j-1]+a[i][j][0];
from2[i][j]=2;
}
else
{
dp2[i][j]=dp2[i-1][j]+a[i][j][0];
from2[i][j]=1;
}
}
if(i==0)
{
dp5[i][j]=dp5[i][j-1]+a[i][j][1];
from5[i][j]=2;
}
else if(j==0)
{
dp5[i][j]=dp5[i-1][j]+a[i][j][1];
from5[i][j]=1;
}
else
{
if(dp5[i][j-1]<dp5[i-1][j])
{
dp5[i][j]=dp5[i][j-1]+a[i][j][1];
from5[i][j]=2;
}
else
{
dp5[i][j]=dp5[i-1][j]+a[i][j][1];
from5[i][j]=1;
}
}
}
}
char ss[2005];
int top = 0;
if(dp2[t-1][t-1]<dp5[t-1][t-1])
{
if(flag == 1 && dp2[t-1][t-1]>1)
{
printf("1\n");
for(int i=0;i<tox;i++)
printf("D");
for(int i=1;i<t;i++)
printf("R");
for(int i=tox+1;i<t;i++)
printf("D");
return 0;
}
printf("%d\n",dp2[t-1][t-1]);
int row=t-1;
int col=t-1;
while(row||col)
{
if(from2[row][col]==2)
{
ss[top++]='R';
col--;
}
else
{
ss[top++]='D';
row--;
}
}
for(int i=top-1; i>=0; i--)
printf("%c",ss[i]);
}
else
{
if(flag == 1 && dp5[t-1][t-1]>1)
{
printf("1\n");
for(int i=0;i<tox;i++)
printf("D");
for(int i=1;i<t;i++)
printf("R");
for(int i=tox+1;i<t;i++)
printf("D");
return 0;
}
printf("%d\n",dp5[t-1][t-1]);
int row=t-1;
int col=t-1;
while(row||col)
{
if(from5[row][col]==2)
{
ss[top++]='R';
col--;
}
else
{
ss[top++]='D';
row--;
}
}
for(int i=top-1; i>=0; i--)
putchar(ss[i]);
}
return 0;
}
题意：给出一个棋盘（三子棋），给出棋盘的情况，'X'是第一个人的棋子，'0'是第二个人的棋子，'.'是空的。来判断棋盘情况是否合法，如果合法，判断是否有人赢，如果没有人赢，如果没人赢且棋盘没满，则输出下一步谁走，否则输出平局。
思路：模拟搞搞搞，说一下我找到的最后一种情况吧，"XXX
00.
. . 0"是不合法的。因为第一个人赢了，游戏就结束了，第二个人就不用下了。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
char ss[5][5];
int ac[3],ar[3],bc[3],br[3],ax[3],bx[3];
int judge()
{
if(ss[0][0]==ss[0][1]&&ss[0][0]==ss[0][2])
{
if(ss[0][0]=='X')
ar[0]=1;
else if(ss[0][0]=='0')
br[0]=1;
}
if(ss[1][0]==ss[1][1]&&ss[1][0]==ss[1][2])
{
if(ss[1][0]=='X')
ar[1]=1;
else if(ss[1][0]=='0')
br[1]=1;
}
if(ss[2][0]==ss[2][1]&&ss[2][0]==ss[2][2])
{
if(ss[2][0]=='X')
ar[2]=1;
else if(ss[2][0]=='0')
br[2]=1;
}
if(ss[0][0]==ss[1][0]&&ss[0][0]==ss[2][0])
{
if(ss[0][0]=='X')
ac[0]=1;
else if(ss[0][0]=='0')
bc[0]=1;
}
if(ss[0][1]==ss[1][1]&&ss[0][1]==ss[2][1])
{
if(ss[0][1]=='X')
ac[1]=1;
else if(ss[0][1]=='0')
bc[1]=1;
}
if(ss[0][2]==ss[1][2]&&ss[0][2]==ss[2][2])
{
if(ss[0][2]=='X')
ac[2]=1;
else if(ss[0][2]=='0')
bc[2]=1;
}
if(ss[0][0]==ss[1][1]&&ss[0][0]==ss[2][2])
{
if(ss[0][0]=='X')
ax[0]=1;
if(ss[0][0]=='0')
bx[0]=1;
}
if(ss[0][2]==ss[1][1]&&ss[2][0]==ss[1][1])
{
if(ss[0][2]=='X')
ax[1]=1;
if(ss[0][2]=='0')
bx[1]=1;
}
// for(int i=0;i<3;i++)
// cout<<ac[i]<<" "<<bc[i]<<" "<<ar[i]<<" "<<br[i]<<endl;
//cout<<ac[0]<<ac[1]<<ac[2]<<ar[0]<<ar[1]<<ar[2]<<ax[0]<<ax[1]<<" "<<bc[0]<<bc[1]<<bc[2]<<br[0]<<br[1]<<br[2]<<bx[0]<<bx[1]<<endl;
if(ac[0]+ac[1]+ac[2]+ar[0]+ar[1]+ar[2]+ax[0]+ax[1]>0&&bc[0]+bc[1]+bc[2]+br[0]+br[1]+br[2]+bx[0]+bx[1]>0)
return 3;
if(ac[0]+ac[1]+ac[2]>1)
return 3;
else if(bc[0]+bc[1]+bc[2]>1)
return 3;
else if(ar[0]+ar[1]+ar[2]>1)
return 3;
else if(br[0]+br[1]+br[2]>1)
return 3;
else if(ac[0]+ac[1]+ac[2]==1)
return 1;
else if(ar[0]+ar[1]+ar[2]==1)
return 1;
else if(br[0]+br[1]+br[2]==1)
return 2;
else if(bc[0]+bc[1]+bc[2]==1)
return 2;
else if(ax[0]+ax[1]>0)
return 1;
else if(bx[0]+bx[1]>0)
return 2;
return 0;
}
int main()
{
#ifdef LOCAL
//freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int aa=0,bb=0;
for(int i=0;i<3;i++)
scanf("%s",ss[i]);
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(ss[i][j]=='X')
aa++;
else if(ss[i][j]=='0')
bb++;
}
}
if(aa-bb>1||aa<bb)
puts("illegal");
else
{
if(aa+bb!=9)
{
int k=judge();
if(k==1)
{
if(aa>bb)
puts("the first player won");
else puts("illegal");
}
else if(k==2)
{
if(aa==bb)
puts("the second player won");
else puts("illegal");
}
else if(k==3)
puts("illegal");
else if(aa>bb)
puts("second");
else puts("first");
}
else
{ int k=judge();
if(aa!=5)
puts("illegal");
else if(k==1)
puts("the first player won");
else if(k==2)
puts("the second player won");
else if(k==3)
puts("illegal");
else puts("draw");
}
}
return 0;
}
题意：给一个三个顶点，问以这三个点为顶点的正N边行（N<=100）的最小面积是多少。
思路：首先找到这个三角形的外切圆的圆心（正弦余弦定理），然后算出半径，然后从三角形开始枚举，到一百边形（边越少面积越小）。我竟然因为开了100*100的数组越界RE，哈哈哈哈
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 13
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
using namespace std;
double corner[105][105] ;
double x[5],y[5];
void init()
{
for(int i = 3 ; i <= 100 ; i ++)
{
corner[i][1] = 2 * PI / (1.0 * i) ;
for(int j = 2 ; j <= i ; j ++)
{
//if(i<10)
corner[i][j]=corner[i][j-1]+corner[i][1];
//cout<<corner[i][j]<<" ";
}
//cout<<endl;
}
}
int main()
{
init();
for(int i = 0 ; i < 3 ; i ++)
{
cin>>x[i]>>y[i];
//cout<<x[i]<<" "<<y[i]<<endl;
}
double a = sqrt ( (x[1] - x[0])*(x[1] - x[0]) + (y[1] - y[0])*(y[1] - y[0]) ) ;
double b = sqrt ( (x[2] - x[0])*(x[2] - x[0]) + (y[2] - y[0])*(y[2] - y[0]) ) ;
double c = sqrt ( (x[2] - x[1])*(x[2] - x[1]) + (y[2] - y[1])*(y[2] - y[1]) ) ;
double cosa = (b * b + c * c - a * a) / (2 * b * c ) ;
double sina = sqrt (1 - cosa * cosa) ;
double r = a / (2 * sina) ;
double aa = asin (a / 2 / r) * 2 ;
double bb = asin (b / 2 / r) * 2 ;
double cc = asin (c / 2 / r) * 2 ;
//printf("%lf %lf %lf\n",aa,bb,cc);
int flag1 = 0 , flag2 = 0 , flag3 = 0;
for(int i = 3 ; i <= 100 ; i ++)
{
flag1 = 0 ;
flag2 = 0 ;
flag3 = 0 ;
for(int j = 1 ; j <= i ; j ++)
{
if(fabs(aa - corner[i][j])<1e-6)
flag1 = 1;
if(fabs(bb - corner[i][j])<1e-6)
flag2 = 1;
if(fabs(cc - corner[i][j])<1e-6)
flag3 = 1;
}
//printf("%d %d %d\n",flag1,flag2,flag3);
if(flag1 + flag2 + flag3 ==3)
{
//cout<< i << endl;
double s = 2 * PI / (1.0 * i) ;
double ledge = sqrt(r * r + r * r - 2 * r * r * cos (s));
//cout<<ledge<<endl;
double p = (r + r + ledge) / 2;
double ans = sqrt(p * (p - r) * (p - r) * (p - ledge)) * (1.0*i);
printf("%.8lf\n",ans);
break;
}
}
return 0;
}
题意：类似括号匹配的问题给出一个括号序列，中间存在问号，如果出现问号，可以选择将它变成‘（’或者‘）’，然后两种变形分别有所花费，问花费最少的能使全括号匹配的方式，不存在输出-1。
思路：从左到右每出现一个‘）’要保证它左边（包括本身）的’（‘数大于等于'）’即可。这样每出现问号直接变成‘）’，如果出现不符合条件的情况就挑左边中一个能增加花费最少的‘？’变成‘（’。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 13
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
char ss[500005];
struct Wenhao {
LL cost;
int pos;
}wenhao;
bool operator < (const Wenhao a,const Wenhao b)
{
return a.cost<b.cost;
}
priority_queue <Wenhao> q ;
int main()
{
scanf("%s",ss);
int len = strlen(ss);
int top = 0 ;
int res = 0 ;
LL ans = 0 ;
for(int i=0;i<len;i++)
{
if(ss[i]=='?')
{
res--;
LL a,b;
scanf("%lld%lld",&a,&b);
wenhao.cost = b - a ;
wenhao.pos = i;
q.push(wenhao);
ss[i] = ')';
ans += b ;
}
else if(ss[i]=='(')
res++;
else res--;
if(res<0)
{
if(!q.empty())
{
ans -= (q.top()).cost;
ss[q.top().pos] = '(';
q.pop();
res+=2;
}
else
{
puts("-1");
return 0;
}
}
}
if(res==0)
{
printf("%lld\n",ans);
puts(ss);
}
else puts("-1");
return 0;
}