A Abs Problem http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5330
找规律题，构造出解。copyright@ts
#include<cstdio>
int main() {
int n,big,sma,id;
while(~scanf("%d",&n)) {
if(n==) {
puts("1 1");
puts("");
puts("");
continue;
}
if(n==) {
puts("1 1");
puts("1 2");
puts("2 1");
continue;
}
if(!((n-)%)||!(n%)) {
sma=;
}
else {
sma=;
}
if(sma) {
if(n&) {
big=n;
id=;
}
else {
big=n-;
id=;
}
}
else {
if(n&) {
big=n-;
id=;
}
else {
big=n;
id=;
}
}
printf("%d %d\n",sma,big);
printf("%d",n);
for(int i=n-;i>=;i--) {
printf(" %d",i);
}
puts("");
if(id==||id==) {
for(int i=n-;i>=;i--) {
printf("%d ",i);
}
printf("%d %d %d\n",n-,n-,n);
}
else {
for(int i=n-; i>=; i--) {
printf("%d ",i);
}
printf("%d\n",n);
}
}
return ;
}
E Easy 2048 Again http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5334
状态压缩dp，只需要存递减的状态。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=;
const int all=<<;
int a[M],dp[][all];
int main(){
int t,n;
int to[];///将输入变成2的x次方
int p2[];///存2的i次方
p2[]=;
for(int i=;i<=;i++){
p2[i]=p2[i-]*;
}
to[]=;
to[]=;
to[]=;
to[]=;
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
a[i]=to[a[i]];
}
mt(dp,-);
int pre=,now=;
dp[pre][]=;
for(int i=;i<=n;i++,now^=,pre^=){
for(int j=;j<all;j++){
if(~dp[pre][j]){
dp[now][j]=max(dp[now][j],dp[pre][j]);///不选
///下面是选
int t=j;///下一个状态
int k=a[i]-;
///dp中第二维0001表示有个2,0011表示有4,2,0111表示8,4,2
int q=(<<k)-;///q为( 比k低一位的位数全是1 )的数
int sum=p2[a[i]];///新得分
if(!(t&q)){///如果比k低的位全是0，才能合并
while((t&(<<k))){
sum+=p2[k+];
k++;
}
q=(<<k)-;
t&=~q;///把比k低的位数全变成0
t|=<<k;
}
else{
t=<<k;///不能合并，产生新递减序列，只有k位是1
}
dp[now][t]=max(dp[now][t],dp[pre][j]+sum);
}
}
}
int ans=;
for(int i=;i<all;i++){
ans=max(ans,dp[pre][i]);
}
printf("%d\n",ans);
}
}
return ;
}
G YY's Minions http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5336
模拟题，怎么说怎么做。
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=;
char op[M];
int mat[][M][M],n,m,f,k,t;
struct G{
int t,x,y;
friend bool operator <(G a,G b){
return a.t<b.t;
}
}g[M*M];
int dx[]={-,-,-,,,,,};
int dy[]={-,,,-,,-,,};
int sum(int x,int y,int pre){
int res=;
for(int i=,tx,ty;i<;i++){
tx=x+dx[i];
ty=y+dy[i];
if(tx>=&&tx<=n&&ty>=&&ty<=m){
if(mat[pre][tx][ty]&){
res++;
}
}
}
return res;
}
int change(int pre,int num){
if(pre==){
if(num==) return ;
return ;
}
if(num==||num==) return ;
return ;
}
char tochar(int x){
if(x==) return 'X';
return x+'';
}
int main(){
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d%d%d",&n,&m,&f,&k);
int pre=,now=;
for(int i=;i<=n;i++){
scanf("%s",op);
for(int j=;j<m;j++){
mat[pre][i][j+]=op[j]-'';
}
}
for(int i=;i<k;i++){
scanf("%d%d%d",&g[i].t,&g[i].x,&g[i].y);
}
sort(g,g+k);
for(int u=,head=;u<=f;u++,pre^=,now^=){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mat[pre][i][j]==){
mat[now][i][j]=;
continue;
}
int num=sum(i,j,pre);
mat[now][i][j]=change(mat[pre][i][j],num);
}
}
while(head<k&&g[head].t==u){
mat[now][g[head].x][g[head].y]=;
head++;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
putchar(tochar(mat[pre][i][j]));
}
putchar('\n');
}
}
}
return ;
}
用vector就不用排序了。
#include<cstdio>
#include<vector>
using namespace std;
const int M=;
char op[M];
int mat[][M][M],n,m,f,k,t;
struct G{
int x,y;
}p;
vector<G> g[M*M];
int dx[]={-,-,-,,,,,};
int dy[]={-,,,-,,-,,};
int sum(int x,int y,int pre){
int res=;
for(int i=,tx,ty;i<;i++){
tx=x+dx[i];
ty=y+dy[i];
if(tx>=&&tx<=n&&ty>=&&ty<=m){
if(mat[pre][tx][ty]&){
res++;
}
}
}
return res;
}
int change(int pre,int num){
if(pre==){
if(num==) return ;
return ;
}
if(num==||num==) return ;
return ;
}
char tochar(int x){
if(x==) return 'X';
return x+'';
}
int main(){
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d%d%d",&n,&m,&f,&k);
int pre=,now=;
for(int i=;i<=n;i++){
scanf("%s",op);
for(int j=;j<m;j++){
mat[pre][i][j+]=op[j]-'';
}
}
for(int i=;i<=f;i++){
g[i].clear();
}
for(int i=,ti;i<k;i++){
scanf("%d%d%d",&ti,&p.x,&p.y);
g[ti].push_back(p);
}
for(int u=,head=;u<=f;u++,pre^=,now^=){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mat[pre][i][j]==){
mat[now][i][j]=;
continue;
}
int num=sum(i,j,pre);
mat[now][i][j]=change(mat[pre][i][j],num);
}
}
int lg=g[u].size();
for(int i=;i<lg;i++){
mat[now][g[u][i].x][g[u][i].y]=;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
putchar(tochar(mat[pre][i][j]));
}
putchar('\n');
}
}
}
return ;
}
H Machine http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5337
树的深搜。邻接表快一些
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=;
struct G{
struct E{
int v,next;
}e[M<<];
int le,head[M];
void init(){
le=;
mt(head,-);
}
void add(int u,int v){
e[le].v=v;
e[le].next=head[u];
head[u]=le++;
}
}g;
vector<int> son[M];
int dfs(int u,int fa){
son[u].clear();
for(int i=g.head[u];~i;i=g.e[i].next){
int v=g.e[i].v;
if(v!=fa){
son[u].push_back(dfs(v,u));
}
}
sort(son[u].begin(),son[u].end());
int res=,ls=son[u].size();
for(int i=;i<ls;i++){
res=max(res,son[u][i]+ls-i-);
}
return res;
}
int main(){
int n;
while(~scanf("%d",&n)){
g.init();
for(int v=,u;v<=n;v++){
scanf("%d",&u);
g.add(u,v);
g.add(v,u);
}
printf("%d\n",dfs(,-));
}
return ;
}
vector慢一些
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int M=;
vector<int> g[M],son[M];
int dfs(int u,int fa){
son[u].clear();
int lu=g[u].size();
for(int i=;i<lu;i++){
int v=g[u][i];
if(v!=fa){
son[u].push_back(dfs(v,u));
}
}
sort(son[u].begin(),son[u].end());
int res=,ls=son[u].size();
for(int i=;i<ls;i++){
res=max(res,son[u][i]+ls-i-);
}
return res;
}
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++){
g[i].clear();
}
for(int v=,u;v<=n;v++){
scanf("%d",&u);
g[u].push_back(v);
g[v].push_back(u);
}
printf("%d\n",dfs(,-));
}
return ;
}
I Incircle and Circumcircle http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5338
机智的用不对的三分过了。定义圆都在y轴，定义三角形一个点在圆心，定义三角形是等腰的。
#include<cstdio>
#include<cmath>
const double eps=1e-;
double r,R;
double f(double y) {
double Y=*R*(-(r*r)/(y*y));
return fabs(Y-y-r);
}
double TernarySearch(double L,double R) { // 三分查找
while(R-L>eps) {
double LL=(L*+R)/;
double RR=(L+R*)/;
if(f(LL)<f(RR)) //f为对应的值 这里求最小值
R=RR;
else
L=LL;
}
return L;
}
int main(){
int t1,t2;
while(~scanf("%d%d",&t1,&t2)){
if(t1*>t2){
puts("NO Solution!");
continue;
}
r=t1;
R=t2;
double ansy=TernarySearch(r,R+R-r);
ansy+=r;
double tmp=ansy-r;
double sinxita=r/tmp;
double cosxita=sqrt(tmp*tmp-r*r)/tmp;
double a=ansy*tmp/sqrt(tmp*tmp-r*r);
double b=a;
double c=*a*r/tmp;
printf("%.18f %.18f %.18f\n",a,b,c);
}
return ;
}
end