Jan.15th
注：黑粗体为超链接
同样是计算几何 Mike你就这么喜欢出计算几何吗
然而看了好久都不知道怎么来
后来去查题解发现是模拟退火。。。
戳我戳我→大白话解析模拟退火
这辈子做过的第一题模拟退火
这题由于是几何所以和这篇里的不太一样：$Eps^{\frac{dE}{kT}}$ 从概率变为了位置的移动
参数我设了0.7 所以比较慢 有些0.5的也能过
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define WA 1e-6 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } struct Point{ double x,y,r; }a[3]; double dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}}; double sqr(double a){return a*a;} double dist(double xa,double ya,double xb,double yb){ return sqrt(sqr(xb-xa)+sqr(yb-ya)); } double Calc(double x,double y){ double Ang[3]; Rep(i,0,2) Ang[i]=dist(x,y,a[i].x,a[i].y)/a[i].r; double ret=0; Rep(i,0,2) ret+=sqr(Ang[(i+1)%3]-Ang[i]); return ret; } int main(){ Rep(i,0,2) a[i].x=IN(),a[i].y=IN(),a[i].r=IN(); double nx=(a[0].x+a[1].x+a[2].x)/3.0; double ny=(a[0].y+a[1].y+a[2].y)/3.0; double T=1.0,nc=Calc(nx,ny); Rep(i,1,2e5){ bool chg=0; double X,Y; Rep(j,0,3){ double x=nx+T*dir[j][0],y=ny+T*dir[j][1]; double xc=Calc(x,y); if (xc<nc){ X=x,Y=y,nc=xc; chg=1; } } if (chg){nx=X,ny=Y;} else T*=0.7; } if (nc<WA) printf("%.10lf %.10lf\n",nx,ny); } |
BFS 没啥好说的
背包问题 因为大小只有1和2 我们就可以贪心了嘛
先排一下序 如果剩下的大小为1的前两个价值最高的加起来没有大小为2的价值最高的价值高就选2否则拿一个1
快没容量的时候特判一下就行
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } struct Car{ int v,idx; bool operator <(const Car&x)const{return v>x.v;} }a1[100005],a2[100005]; int cnt1,cnt2,n,v,cnt,Ans[100005],Ansv; void Put1(int &z1){ Ansv+=a1[z1].v; Ans[++cnt]=a1[z1].idx; v--;z1++; } void Put2(int &z2){ Ansv+=a2[z2].v; Ans[++cnt]=a2[z2].idx; v-=2;z2++; } int main(){ n=IN(),v=IN(); cnt1=cnt2=0; Rep(i,1,n){ int t=IN(),p=IN(); if (t==1) a1[++cnt1].v=p,a1[cnt1].idx=i; else a2[++cnt2].v=p,a2[cnt2].idx=i; } a1[cnt1+1].v=0; sort(a1+1,a1+cnt1+1); sort(a2+1,a2+cnt2+1); int z1=1,z2=1; while (z1<=cnt1||z2<=cnt2){ if (!v) break; if (v==1){ if (z1<=cnt1) Put1(z1); break; } else{ if (z1>cnt1) Put2(z2); else if (z2>cnt2) Put1(z1); else if (a1[z1].v+a1[z1+1].v<a2[z2].v) Put2(z2); else Put1(z1); } } printf("%d\n",Ansv); Rep(i,1,cnt) printf("%d ",Ans[i]); } |
先每天全部最少时间 然后一天天向上加就好了
字符串处理题……一开始看错了
后来发现只有小写字母
不就SB题了么 map搞一搞
先把放不下卡片的筛掉
然后排下序$n^2$做一下DP就行了
记录一下序列
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } struct Env{ int w,h,idx,mxl,p; bool operator <(const Env&x)const{return w==x.w?h<x.h:w<x.w;} }a[5005]; void Print(int pos){ if (a[pos].mxl>1) Print(a[pos].p); printf("%d ",a[pos].idx); } int n,w,h,cnt; int main(){ n=IN(),w=IN(),h=IN(); cnt=0; Rep(i,1,n){ int W=IN(),H=IN(); if (W>w&&H>h){ a[++cnt].w=W; a[cnt].h=H; a[cnt].idx=i; } } n=cnt; sort(a+1,a+n+1); Rep(i,1,n) a[i].mxl=1; Rep(i,2,n){ Rep(j,1,i-1){ if (a[j].w==a[i].w) break; if (a[j].h<a[i].h&&a[j].mxl+1>a[i].mxl){ a[i].mxl=a[j].mxl+1; a[i].p=j; } } } int Max=0,pos; Rep(i,1,n) if (a[i].mxl>Max) Max=a[i].mxl,pos=i; printf("%d\n",Max); if (Max) Print(pos); } |
大特判！
评论 (0)
