怎麽做网站,电子商务网站商品怎么来,设计logo 费用,房屋装修网站模板心得
赛中ac#xff1a;5#xff0c;目前ac#xff1a;9#xff0c;题目总数#xff1a;13
中档可做题还是很多的#xff0c;可惜遇到了难绷的queueforces#xff0c;
最后15min才判出来#xff0c;oi赛制5wa4遗憾离场#xff0c;赛后把几个题都给调过了#xff0…心得
赛中ac5目前ac9题目总数13
中档可做题还是很多的可惜遇到了难绷的queueforces
最后15min才判出来oi赛制5wa4遗憾离场赛后把几个题都给调过了写下题解 题目
J. Breakfast签到
签到不过不是很懂python直接输出39.20为啥wa了
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
int n,m;
int main(){sci(n),sci(m);printf(%.2lf\n,0.6*nm);return 0;
}
A. Paper Watering枚举
先特判1
对于非1的情况首先原数是可以一直平方不重的
如果x开根号遇到了下取整说明sqrt(x)*sqrt(x)也不会和x重后续平方也都不会重
暴力模拟这个过程直至出现1为止
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
int x,k;
ll ans;
int main(){sci(x),sci(k);if(x1){puts(1);return 0;}ansk1;rep(i,1,k){int vsqrt(x);if(vx)break;if(1ll*v*vx){ans;}else{if(v1)ans;else ans1k-i;}xv;}ptlle(ans);return 0;
}
D. nIM gAME博弈
发现后手可以控制倒数第二张牌取什么从而使先手必败
//#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
int t,n;
int main(){sci(t);while(t--){sci(n);puts(lose);}return 0;
}
E. Checksum枚举
枚举最终的d有几个1从而唯一确定后缀补的1的数量和位置输出即可
//#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N2e510;
int t,n,k;
char s[N];
int main(){sci(t);while(t--){sci(n);sci(k);scanf(%s,s1);int c0;rep(i,1,n)c(s[i]1);int ans1e9;rep(j,c,ck){int vj((1k)-1);if(__builtin_popcount(v)j-c){ansmin(ans,v);}}if(ans1e9)puts(None);else{per(j,k-1,0){printf(%1d,ansj1);}puts();}}return 0;
}
L. Bracket Generation计数 一开始把第二个条件看错了以为只有内层的选完了外层的才能选没有这个限制之后就很好做
把左右括号相邻的()括号称为叶子节点建括号树更直观其他的称为非叶节点
非叶节点能选当且仅当其包含的最大叶子结点x及序列里位于x左侧的叶子结点都选完之后才能选
将序列倒着考虑就是非叶节点的一个插空问题
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N2e610,M2*N,mod998244353;
char s[N];
int n,cnt,lim[N];
int main(){scanf(%s,s1);nstrlen(s1);rep(i,1,n){if(s[i]) s[i-1]()cnt;if(s[i]) s[i-1]!(){lim[i]cnt;}}int now0,ans1;per(i,n,1){if(!lim[i])continue;ans1ll*ans*(cnt-lim[i]now1)%mod;now;}pte(ans);return 0;
}
F. Factor数论 先把p、k分别质因数分解求出对应质因数和出现的幂次
对于p的质因子f如果f也是k的质因子显然出现多少次都无所谓都能除尽删掉这些f
对于p的独有质因子也就是没有出现在k中的质因子p1、p2、…
记每个的最高幂次是k1、k2、…将这些最高幂次乘起来得到y 枚举y的因子z也就是这些独有质因子出现了多少
分母必须恰好能和z兑掉且剩下的部分由k出现过的质因子构成
在[1,x/z]内仅由k出现过的质因子构成的数这个可以先预处理出所有再二分
因为仅由质因子组成所以数量没有太多
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int maxp 1e710;
int t, tot, pr[maxp], d[maxp];
ll p,x,k,now,ans;
vectorPf,f2;
vectorllg,all;
mapll,boolmp;
void dfs(ll v,int y){all.pb(v);int szSZ(g);for(int iy;isz;i){if(1ll*vx/g[i])dfs(v*g[i],i);}
}
void sol(ll v,int y,int z){ansupper_bound(all.begin(),all.end(),x/v)-all.begin();int szSZ(f2);if(ysz)return;//printf(v:%lld y:%d z:%d fi:%lld se:%d\n,v,y,z,f2[y].fi,f2[y].se);if(1ll*vx/f2[y].fi z1f2[y].se)sol(v*f2[y].fi,y,z1);for(int iy1;isz;i){if(1ll*vx/f2[i].fi)sol(v*f2[i].fi,i,1);}
}
int main(){for(int i 2; i maxp; i) {if(!d[i])pr[tot] d[i] i;for(int j 0, z; (z i * pr[j]) maxp; j) {d[z] pr[j];if(d[i] pr[j])break;}}scanf(%lld%lld%lld,p,x,k);rep(i,0,tot-1){if(1ll*pr[i]*pr[i]p){break;}if(p%pr[i]0){f.pb(P(pr[i],0));while(p%pr[i]0)p/pr[i],f.back().se;}}if(p1)f.pb(P(p,1));//for(auto x:f)printf((p:%lld,c:%lld)\n,x.fi,x.se);rep(i,0,tot-1){if(1ll*pr[i]*pr[i]k){break;}if(k%pr[i]0){g.pb(pr[i]);mp[pr[i]]true;while(k%pr[i]0)k/pr[i];}}if(k1){g.pb(k);mp[k]true;}//for(auto x:g)printf((g:%lld)\n,x);for(auto v:f){if(mp.count(v.fi))continue;f2.pb(v);}//for(auto v:f2)printf((%lld,%lld) ,v.fi,v.se);puts();dfs(1,0);sort(all.begin(),all.end());//for(auto v:all)printf((v:%lld)\n,v);sol(1,0,0);ptlle(ans);return 0;
}
I. Passworddp dp[i]表示[1,i]是合法答案的方案数
转移枚举最后一段的长度x最后这一段和前面的x-k共同拼成了一个长度为k的排列
但是枚举长度为2的时候会和长度为1的方案有重复具体来说
不妨k5前5个肯定只能是一个排列k!种方案不妨是1 2 3 4 5对于第6个往后
对于x11 2 3 4 5 [1]
x21 2 3 4 5 [2 1]和 1 2 3 4 5 [1 2]中只能保留第一个因为第二个和x1重复了
x3同理只能保留1 2 3 4 5 [3 1 2]、1 2 3 4 5 [3 2 1]和1 2 3 4 5 [2 3 1] 这个系数是需要递推减掉的手玩发现
记长度为x的系数是xs[x]对于长度x来说若yx则需要在总数里减掉xs[y]*fac[x-y] rep(i,1,k){ xs[i]fac[i]; per(j,i-1,1){ xs[i](xs[i]mod-1ll*xs[j]*fac[i-j]%mod)%mod; } //printf(i:%d xs:%d\n,i,xs[i]); } O(k^2)预处理出系数之后再O(nk)dp即可
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N1e510,K1e310,mod998244353;
int n,k;
int xs[K],Finv[N],fac[N],inv[N],dp[N];
void init(int n){ //nNinv[1]1;for(int i2;in;i)inv[i]1ll*(mod-mod/i)*inv[mod%i]%mod;fac[0]Finv[0]1;for(int i1;in;i)fac[i]1ll*fac[i-1]*i%mod,Finv[i]1ll*Finv[i-1]*inv[i]%mod;//Finv[n]modpow(fac[n],mod-2,mod);//for(int in-1;i1;--i)Finv[i]1ll*Finv[i1]*(i1)%mod;
}
int main(){sci(n),sci(k);if(nk){puts(0);return 0;}init(n);dp[k]fac[k];//printf(n:%d k:%d\n,n,k);rep(i,1,k){xs[i]fac[i];per(j,i-1,1){xs[i](xs[i]mod-1ll*xs[j]*fac[i-j]%mod)%mod;}//printf(i:%d xs:%d\n,i,xs[i]);}rep(i,k1,n){for(int j1;jk;j){dp[i](dp[i]1ll*dp[i-j]*xs[j]%mod)%mod;}// printf(i:%d dp:%d\n,i,dp[i]);//dp[i](dp[i-1]*fac[1]dp[i-2]*(fac[2]-fac[1])dp[i-3]*(fac[3]-fac[2])...dp[i-k]*(fac[k]-fac[k-1]))//dp[i-1](dp[i-2]*fac[1]dp[i-3]*(fac[2]-fac[1])dp[i-4]*(fac[3]-fac[2])...dp[i-k-1]*(fac[k]-fac[k-1]))//dp[i]-dp[i-1]dp[i-1]-dp[i-2]dp[i-2]dp[i-3]...dp[i-k]-dp[i-k-1];//dp[i](2ll*dp[i-1]%mod-dp[i-k-1]mod)%mod;}pte(dp[n]);return 0;
}
M. House计算几何 感觉计算几何的题平时不怎么写所以不太会写
但实际上出题人应该平时也不怎么写出的题还是挺基础的 先求出矩形O(n^2logn)枚举点对将点对放入线段中点线段长度的map内
矩形的对角线互相平分所以共用中点且长度相等的两条对角线能构成一个矩形 两两枚举矩形对于矩形四条边任意两条邻边x、y检查一下
统计房子在x外侧的第五个点的个数这个需要叉积判断不在矩形内部 此时需要统计向量i-j左侧/右侧有多少点O(n^3)预处理一下即可
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,ll P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)const int N305,MN*N;
using i64 long long;
using T long long;int n,c;
ll res;struct Point {T x;T y;Point(T x 0, T y 0) : x(x), y(y) {}Point operator(const Point p) {x p.x, y p.y;return *this;}Point operator-(const Point p) {x - p.x, y - p.y;return *this;}Point operator*(const T v) {x * v, y * v;return *this;}friend Point operator-(const Point p) {return Point(-p.x, -p.y);}friend Point operator(Point lhs, const Point rhs) {return lhs rhs;}friend Point operator-(Point lhs, const Point rhs) {return lhs - rhs;}friend Point operator*(Point lhs, const T rhs) {return lhs * rhs;}
}e[N];T dot(const Point a, const Point b) {return a.x * b.x a.y * b.y;
}T cross(const Point a, const Point b) {return a.x * b.y - a.y * b.x;
}maparrayll,3,vectorPmp;
vectorPans[M];
int pos[N][N],neg[N][N];
void ck(int a,int b,int c){//printf(a:%d b:%d c:%d res1:%lld\n,a,b,c,res);if(cross(e[c]-e[b],e[a]-e[b])0)respos[b][a];else resneg[b][a];//printf(a:%d b:%d c:%d res2:%lld\n,a,b,c,res);
}int main(){sci(n);rep(i,1,n){scanf(%lld%lld,e[i].x,e[i].y);}rep(i,1,n){rep(j,1,n){if(ij)continue;Point ce[i]-e[j];ll zdot(c,c);//printf(i:%d j:%d x:%lld y:%lld z:%lld\n,i,j,e[i].xe[j].x,e[i].ye[j].y,z);if(ij)mp[{e[i].xe[j].x,e[i].ye[j].y,z}].pb(P(i,j));rep(k,1,n){if(ik||jk)continue;Point kie[k]-e[i],kje[k]-e[j];ll xdot(ki,ki),ydot(kj,kj);if(xy){ll wcross(e[k]-e[i],e[j]-e[i]);if(w0){//printf(i:%d j:%d neg:%d\n,i,j,neg[i][j]);pos[i][j];//i-j的逆时针方向 样例房子形状}else if(w0){neg[i][j];//printf(i:%d j:%d neg:%d\n,i,j,pos[i][j]);}}}}}for(auto x:mp){ans[c]x.se;}// rep(i,1,n){// rep(j,1,n){// if(ij)continue;// printf(i:%d j:%d neg:%d pos:%d\n,i,j,neg[i][j],pos[i][j]);// }// }rep(i,1,c){int szSZ(ans[i]);rep(j,0,sz-1){rep(k,j1,sz-1){int aans[i][j].fi,dans[i][j].se,bans[i][k].fi,cans[i][k].se;//printf(a:%d b:%d c:%d d:%d res:%lld\n,a,b,c,d,res);ck(b,a,c);ck(a,c,d);ck(c,d,b);ck(d,b,a);//printf(a:%d b:%d c:%d d:%d res2:%lld\n,a,b,c,d,res);}}}ptlle(res);return 0;
}
/*
5
4 2
0 2
2 5
4 0
0 0
*/
G. Diamond分块 想到分块之后就很好做了虽然空间稍微用short卡了一下
先把n弥补成块的倍数方便后面判断后面的都用0补足即可 对于第i个块预处理出块内任意两种数(x,y)的逆序对个数
计在这个块内x、y出现的第一个位置big[i][x][y] 所以也需要记录每种数x在第i个块内出现的第一个位置pos[x][i]是多少
这个位置可以对块长取模就是一个最大为块长M300多的数short足矣 然后就是在线查询
对于长度不超过3*M的块懒得分类讨论有一个块还是两个了直接暴力常数略大一点而已
超过3*M的一定中间有完整块然后最多两个半块
对于每个完整块先加上完整块的答案对于半块暴力统计答案
再从前往后、从后往前遍历块分别统计块间能产生的答案求和即可
#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includeset
#includequeue
#includeunordered_map
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N1e51e410,M340;
short pos[N][M];
int big[M][M][M];
int n,T,a[N],l,r,p,q,sq,sz[M][M];
int main(){sci(n),sci(T);sqsqrt(n);//printf(sq:%d\n,sq);memset(pos,-1,sizeof pos);rep(i,0,n-1){sci(a[i]);int xi/sq;if(pos[a[i]][x]-1){pos[a[i]][x]i%sq;//printf(i:%d ai:%d x:%d pos:%d\n,i,a[i],x,pos[a[i]][x]);}}while(n%sq)n;rep(i,0,(n-1)/sq){int li*sq,r(i1)*sq-1;//printf(i:%d l:%d r:%d\n,i,l,r);rep(j,l,r){sz[i][pos[a[j]][i]];rep(k,j1,r){if(a[k] a[j]a[k]){int p1pos[a[j]][i],p2pos[a[k]][i];big[i][p1][p2];//printf(i:%d aj:%d ak:%d p1:%d p2:%d big:%d\n,i,a[j],a[k],p1,p2,big[i][p1][p2]);}}}}while(T--){sci(l),sci(r),sci(p),sci(q);l--;r--;if(pq)swap(p,q);ll ans0,cp0,cq0;if(r-l13*sq){rep(i,l,r){if(a[i]p)cp;else if(a[i]q)anscp;}ptlle(ans);continue;}int xl/sq*sqsq-1,yr/sq*sq;rep(i,l,x){if(a[i]p)cp;else if(a[i]q)anscp;}per(i,r,y){if(a[i]q)cq;else if(a[i]p)anscq;}rep(i,(x1)/sq,(y-1)/sq){int p1pos[p][i],p2pos[q][i],v10,v20;if(~p1)v1sz[i][p1];if(~p2)v2sz[i][p2];if(~p1 ~p2)ansbig[i][p1][p2];ans1ll*cp*v2;cpv1;}ans1ll*cp*cq;ptlle(ans);}return 0;
}
