建立自信,外贸seo推广,中国新闻最新消息简要,免费的网页入口牛客网暑期ACM多校训练营#xff08;第三场#xff09; A. PACM Team 01背包#xff0c;输出方案#xff0c;用bool存每种状态下用的哪一个物品#xff0c;卡内存。官方题解上#xff0c;说用char或者short就行了。还有一种做法是把用的物品压成一个int。 #include b… 牛客网暑期ACM多校训练营第三场 A. PACM Team 01背包输出方案用bool存每种状态下用的哪一个物品卡内存。官方题解上说用char或者short就行了。还有一种做法是把用的物品压成一个int。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
typedef long double LD;
using namespace std;
int n,p[37],a[37],c[37],m[37],g[37],A,C,M,P,ans 0;
int dp[37][37][37][37];
bool usd[37][37][37][37][37];
int v[40],cnt0,vis[40];
int main() {int tp0,ta0,tc0,tm0,tmp0;scanf(%d,n);rep(i,0,n-1) {scanf(%d%d%d%d%d,p[i],a[i],c[i],m[i],g[i]);}scanf(%d%d%d%d,P,A,C,M);dp[0][0][0][0] tmp;rep(i,0,n-1) {per(ip,P,p[i])per(ia,A,a[i])per(ic,C,c[i])per(im,M,m[i]) {int t 0,t2 dp[ip-p[i]][ia-a[i]][ic-c[i]][im-m[i]] g[i];t dp[ip][ia][ic][im];if(t t2) {dp[ip][ia][ic][im] t2;usd[ip][ia][ic][im][i] 1;}}}tp P; ta A; tc C; tm M;per(i,n-1,0) if(tp0ta0tc0tm0) {if(usd[tp][ta][tc][tm][i]) {v[cnt]i;tp-p[i];ta-a[i];tc-c[i];tm-m[i];}}sort(v1,v1cnt);printf(%d\n,cnt);int f0;if(cnt) {for(int i1;icnt;i) {if(f)printf( );f1;printf(%d,v[i]);}puts();}return 0;
}C. Shuffle Cards 每次把中间一段数字移到开头。学习了rope的用法。然后写了个块链。。。t到爆炸。 rope: push_back(x);//在末尾添加x insert(pos,x);//在pos插入x自然支持整个char数组的一次插入 erase(pos,x);//从pos开始删除x个 copy(pos,len,x);//从pos开始长度为len用x代替 replace(pos,x);//从pos开始换成x substr(pos,x);//提取pos开始x个 at(x)/[x];//访问第x个元素 rope做法 #include bits/stdc.h
#include ext/rope
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 1e6 7;
using namespace std;
using namespace __gnu_cxx;
int n,m;
ropeint s;
int main() {scanf(%d%d,n,m);rep(i,1,n) s.pb(i);rep(i,1,m) {int p,x;scanf(%d%d,p,x);s s.substr(p-1,x) s.substr(0,p-1) s.substr(px-1,n-(px-1));}int f0;rep(i,0,n-1) {if(f)printf( );f1;printf(%d,s[i]);}puts();return 0;
} 块链做法 //listblock TLE#include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 300010;
const int M 1000 7;
using namespace std;
int n,m,B,num,hd;
struct listBlock{vectorint s;int nxt,pre;void init(){s.clear();nxtpre0;}void ins(int x) {s.pb(x);}
}block[N];
void init(int s[]) {B sqrt(n);num n/B; if(n%B)num;hd0;block[hd].nxt 1;rep(i,1,num) block[i].init(),block[i].nxti1,block[i].prei-1;block[num].nxt -1;rep(i,0,n-1) block[i/B1].ins(s[i]);
}
void split(int x,int p) {//(l[x],p)(p1,r[x])if(p(int)block[x].s.size()-1)return;int n (int)block[x].s.size();listBlock tmp block[x];block[x].init();rep(i,0,p)block[x].ins(tmp.s[i]);block[x].pre tmp.pre;block[x].nxt num1;num; block[num].init();rep(i,p1,n-1)block[num].ins(tmp.s[i]);block[num].pre x;block[num].nxt tmp.nxt;block[tmp.pre].nxt x;block[tmp.nxt].pre num;tmp.init();
}
int fd(int x,int sum) {sum0;for(int ihd;i!-1;iblock[i].nxt) {sum(int)block[i].s.size();if(sumx) return i;}return 0;
}
void pt(int x) {printf(%d block:\n,x);printf(sz: %d\n,block[x].s.size());rep(i,0,block[x].s.size()-1)printf(%d ,block[x].s[i]);puts();printf(nxt: %d\n,block[x].nxt);printf(pre: %d\n,block[x].pre);
}
int merge(int x,int y) {if(xy)return x;if(x-1||y-1||xhd||yhd)return x;rep(i,0,(int)block[y].s.size()-1)block[x].ins(block[y].s[i]);block[x].nxt block[y].nxt;block[block[y].nxt].pre x;block[y].init();return x;
}
void adpt() {for(int ihd;i!-1;iblock[i].nxt) {if(i!hdblock[i].nxt!-1(int)block[i].s.size()(int)block[block[i].nxt].s.size() B) {i merge(i,block[i].nxt);}}
}
void solve(int l,int r) {int suml0,sumr0;int pl fd(l,suml);int pr fd(r,sumr);if(lsuml-(int)block[pl].s.size()1) split(pl,l-(suml-(int)block[pl].s.size())-1-1);if(rsumr) split(pr,r-(sumr-(int)block[pr].s.size())-1);pl fd(l,suml);pr fd(r,sumr);block[block[pl].pre].nxt block[pr].nxt;block[block[pr].nxt].pre block[pl].pre;block[block[hd].nxt].pre pr;block[pl].pre hd;block[pr].nxt block[hd].nxt;block[hd].nxt pl;
}
int s[N];
int main() {scanf(%d%d,n,m);for(int i0;in;i) s[i]i1;init(s);rep(i,1,m) {int l,r,p;scanf(%d%d,l,p);r lp-1;solve(l,r);adpt();}int f0;for(int ihd;~i;iblock[i].nxt) {if(i!hd) {for(int j0;j(int)block[i].s.size();j) {if(f)printf( );f1;printf(%d,block[i].s[j]);}}}puts();return 0;
}E. Sort String 这句话脑抽读不懂。。。就查了下中文题意 For each i in [0,|S|-1], let Si be the substring of S starting from i-th character to the end followed by the substring of first i characters of S. Index of string starts from 0. 就是我把这个串循环移位把相同的分在一组输出。 做法就是kmp找循环节如果这个串不是周期串则每个位置都不在一组否则就把一个周期拆开即可。难点真的在读题。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 1e6 7;
using namespace std;
int len,nxt[N];
char s[N];
void getnxt() {int i0,j;jnxt[0]-1;while(ilen) {while(j!-1s[i]!s[j])jnxt[j];nxt[i]j;}
}
int main() {scanf( %s,s);len strlen(s);getnxt();int t len - nxt[len];if(len%t) {printf(%d\n,len);rep(i,0,len-1)printf(1 %d\n,i);}else {printf(%d\n,t);rep(i,0,t-1) {printf(%d,len/t);for(int ji;jlen;jt)printf( %d,j);puts();}}return 0;
}G. Coloring Tree 还是不太理解。。 大佬题解 H. Diff-prime Pairs 先保证i小于j打了个表发现对于素数j与他配对的就是它比他小的所有素数对于合数与他配对的就是它的所有素因子的配对之和。于是考虑每个素数x对答案的贡献就是能整除x的数乘上比他小的素数的个数最后乘2
#include bits/stdc.h
typedef long long ll;
const int N 10000000;
using namespace std;
ll ans0,num0;
int n,phi[N1],notp[N1],p[N1];
void init() {notp[1]1;for(int i2; in; i) {if(!notp[i]) p[p[0]] i;for(int j1; jp[0] i*p[j]n; j) {notp[i*p[j]] 1;if(i%p[j] 0) break;}}
}int main() {scanf(%d,n);init();for(int i1;in;i) if(!notp[i]){ans (n/i)*num;num;}printf(%lld\n,ans*2LL);return 0;
}I. Expected Size of Random Convex Hull 一开始读错题拿pick定理搞了半天。。。因为n十分的小于是直接随机然后取平均。然后写了锐角坐标系中的随机取点。WA了之后发现答案好像与三角形的形状无关感性思考一下任何一种点的分布都可以通过线性变换成为另一个三角坐标系中的点。所以答案与n相关那就可以打表了。三角形直接取最简单的沿xy轴的等腰直角三角形让边长尽可能长。然后我的写法每种n随机了1e8次精度才够。(好像是因为ans手残定义成了long double #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
typedef long double LD;
const int lim 100000005;
using namespace std;
struct point{double x,y;point operator (const point a)const {point t;t.x a.xx, t.y a.yy;return t;}point operator - (const point a)const {point t;t.x x - a.x, t.y y - a.y;return t;}
}p[3],v[12];
int n,cnt;
point mkp() {point C;C.x ((double)rand())/RAND_MAX;C.y ((double)rand())/RAND_MAX;return C;
}
struct Line_segment {point s,e;Line_segment() {}Line_segment(point a,point b):s(a),e(b) {}
};
double multiply(point sp,point ep,point op) {return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}bool cmp1(point a,point b) {if(a.x b.x) return a.y b.y;return a.x b.x;
}
point res[22];
int graham(point pnt[],int n,point res[]) {sort(pnt,pntn,cmp1);int m0, k;for(int i 0; i n; i) {while(m1 multiply(res[m-1],pnt[i],res[m-2])0) m--;res[m]pnt[i];}k m;for(int i n-2; i 0; i--) {while(mk multiply(res[m-1],pnt[i],res[m-2])0) m--;res[m]pnt[i];}if(n 1) m--;return m;
}
void getpoint() {for(int i0;in;i) {point p1 mkp();if(p1.xp1.y)swap(p1.x,p1.y);v[i]p1;}
}
int tubao() {return graham(v,n,res);
}
double a[]{0,0,0,3.000000,3.6667248067,4.1667674917,4.5667089017,4.9000191650,5.1856561607,5.4356834882,5.6579956371};
int main() {//freopen(out.txt,w,stdout);rep(i,0,2)scanf(%lf%lf,p[i].x,p[i].y);scanf(%d,n);
// for(n3;n10;n) {
// srand(time(0));
// LD ans 0;
// rep(ti,1,lim) {
// getpoint();
// int tmp tubao();
// ans tmp;
// }
// printf(%.10f\n,(double)ans/lim);
// }printf(%.10f\n,a[n]);return 0;
}J. Distance to Work 就是二分半径然后圆和多边形交。然而我的板子精度疯狂被卡。。。网上贴了一份就过了。。。计算几何都是送命题啊。(换了的kuangbin神犇的板子测试了一下应该比较稳。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
const double eps 1e-8;
const double inf 1e20;
const double pi acos(-1.0);
const int maxp 1010;
using namespace std;
int sgn(double x) {if(fabs(x) eps) return 0;if(x 0) return -1;else return 1;
}
struct Point {double x,y;Point(){}Point(double _x,double _y){x_x;y_y;}void input() {scanf(%lf%lf,x,y);}bool operator (Point b) const{return sgn(x-b.x) 0 sgn(y-b.y) 0;}bool operator (Point b) const{return sgn(x-b.x)0?sgn(y-b.y)0:xb.x;}Point operator - (const Point b) const {return Point(x-b.x,y-b.y);}double operator ^ (const Point b) const {return x*b.y - y*b.x;}double operator * (const Point b) const {return x*b.x y*b.y;}Point operator * (const double k) const {return Point(x*k,y*k);}Point operator / (const double k) const {return Point(x/k,y/k);}Point operator (const Point b) const {return Point(xb.x,yb.y);}double len() {return hypot(x,y);}double len2() {return x*xy*y;}double distance(Point p) {return hypot(x-p.x,y-p.y);}double rad(Point a,Point b) {Point p *this;return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));}Point trunc(double r) {double l len();if(!sgn(l)) return *this;r / l;return Point(x*r,y*r);}
};
struct Line {Point s,e;Line(){}Line(Point _s,Point _e){s_s;e_e;}double length(){return s.distance(e);}double dispointtoline(Point p) {return fabs((p-s)^(e-s))/length();}Point lineprog(Point p) {return s ( ((e-s)*((e-s)*(p-s)))/(e-s).len2() );}
};struct circle {Point p;double r;circle(){}circle(Point _p,double _r){p_p;r_r;}int relation(Point b) {double dst b.distance(p);if(sgn(dst-r)0) return 2;else if(sgn(dst-r)0) return 1;return 0;}int relationline(Line v) {double dst v.dispointtoline(p);if(sgn(dst-r)0)return 2;else if(sgn(dst-r)0)return 1;return 0;}int pointcrossline(Line v,Point p1,Point p2) {if(!(*this).relationline(v)) return 0;Point a v.lineprog(p);double d v.dispointtoline(p);d sqrt(r*r-d*d);if(sgn(d)0) {p1a;p2a;return 1;}p1 a (v.e-v.s).trunc(d);p2 a - (v.e-v.s).trunc(d);return 2;}double areatriangle(Point a,Point b) {if(sgn((p-a)^(p-b)) 0) return 0.0;Point q[5];int len 0;q[len] a;Line l(a,b);Point p1,p2;if(pointcrossline(l,q[1],q[2]) 2) {if(sgn((a-q[1])*(b-q[1])) 0) q[len] q[1];if(sgn((a-q[2])*(b-q[2])) 0) q[len] q[2];}q[len] b;if(len 4 sgn((q[0]-q[1])*(q[2]-q[1]))0) swap(q[1],q[2]);double res 0;rep(i,0,len-2) {if(relation(q[i]) 0||relation(q[i1]) 0) {double arg p.rad(q[i],q[i1]);res r*r*arg*0.5;}else {res fabs((q[i]-p)^(q[i1]-p))*0.5;}}return res;}
};struct polygon {int n;Point p[maxp];void input(int _n) {n _n;rep(i,0,n-1) p[i].input();}double getarea() {double sum 0;rep(i,0,n-1)sum (p[i]^p[(i1)%n]);return fabs(sum)*0.5;}double areacircle(circle c) {double ans 0;rep(i,0,n-1) {int j (i1)%n;if(sgn((p[j]-c.p)^(p[i]-c.p)) 0)ans c.areatriangle(p[i],p[j]);elseans - c.areatriangle(p[i],p[j]);}return fabs(ans);}
};int n,q;
double Sp;
polygon P;
double solve(Point s,double PP,double Q) {double l 0, r 1e7,mid;int TT200;while(TT--) {mid (lr)/2.0;circle c;c.p s; c.r mid;double t P.areacircle(c);if(t*QSp*(Q-PP)) lmid;else r mid;}return l;
}int main() {scanf(%d,n);P.input(n);Sp P.getarea();scanf(%d,q);while(q--) {Point s;double PP,Q;s.input();scanf(%lf %lf,PP,Q);printf(%.10f\n,solve(s,PP,Q));}return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9379778.html
