霸州建设局网站,网站认证怎么做,wordpress 专题页,做网站的开场白A.小乔和小灰灰
前几天刚刚学了序列自动机#xff0c;这题直接也没咋想暴力的做法#xff0c;直接上序列自动机匹配子序列即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm这题直接也没咋想暴力的做法直接上序列自动机匹配子序列即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
const int N1010;
char s[N];
int ne[N][110],n;
char p1[]XiaoQiao;
char p2[]XiaoHuiHui;
void build()
{for(int in;i;i--){for(int j0;j100;j)ne[i-1][j]ne[i][j];ne[i-1][s[i]-A]i;}
}
int main()
{IO;int T1;//cinT;while(T--){cins1;nstrlen(s1);build();bool ok11,ok21;for(int i0,now0;i8;i){nowne[now][p1[i]-A];if(!now) {ok10;break;}}for(int i0,now0;i10;i){nowne[now][p2[i]-A];if(!now) {ok20;break;}}if(ok1ok2) coutHappy\n;else coutemm\n;}return 0;
}B.牛能和小镇
∣xi2yi−xj2yjyi2(yi−2xi)−yj2(yj−2xj)∣|x_i^2y_i-x_j^2y_jy_i^2(y_i-2x_i)-y_j^2(y_j-2x_j)|∣xi2yi−xj2yjyi2(yi−2xi)−yj2(yj−2xj)∣ 不难发现这个式子iii和jjj之间的坐标没有任何相关性我们做一步转化 ∣xi2yiyi2(yi−2xi)−(xj2yjyj2(yj−2xj))∣|x_i^2y_iy_i^2(y_i-2x_i)-(x_j^2y_jy_j^2(y_j-2x_j))|∣xi2yiyi2(yi−2xi)−(xj2yjyj2(yj−2xj))∣ 发现要把每个点用一个坐标表示即可xi2yiyi2(yi−2xi)x_i^2y_iy_i^2(y_i-2x_i)xi2yiyi2(yi−2xi)然后二维转化成一维数轴上的点连接就非常容易了
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N100010;
ll p[N];
int n;
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i){ll x,y;cinxy;p[i]x*x*yy*y*(y-2*x);}sort(p1,p1n);coutp[n]-p[1]\n;}return 0;
}C.装备合成
典型数学题目直接像做高中线性规划题做即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long ll;
typedef pairint,int pii;
typedef unsigned long long ull;
const int N100010;
ll x,y;
bool check(ll a,ll b)
{return (2*a4*bx)(3*aby);
}
int main()
{IO;int T1;cinT;while(T--){cinxy;ll a(4*y-x)/10;ll b(3*x-2*y)/10;if(a0b0){ll res0;if(check(a,b)) resmax(res,ab);if(check(a,b1)) resmax(res,ab1);if(check(a1,b)) resmax(res,ab1);if(check(a,b-1)) resmax(res,ab-1);if(check(a-1,b)) resmax(res,ab-1);coutres\n;}else if(a0)coutmin(x/4,y)\n;else if(b0) coutmin(x/2,y/3)\n;else cout0\n;}return 0;
}D.取石子游戏
暴力打表总结规律瞎胡搞 毕竟我也看不出啥规律啊~~
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
using namespace std;
typedef long long ll;
typedef pairint,int pii;
typedef unsigned long long ull;
const int N100010;
ll sg[N];
ll dfs(ll u)
{if(sg[u]!-1) return sg[u];if(u1) return sg[u]0;int adfs(u/2);int bdfs((u1)/2);for(int i0;;i)if(i!ai!b) return sg[u]i;
}ll f[N],s[N];
int sz;
void init()
{f[1]1;f[2]2;s[1]1;s[2]3;for(int i3;;i){f[i]f[i-1]s[i-2];if(i%20) f[i];s[i]f[i]s[i-1];if(s[i]1e18){szi;break;}}
}
int main()
{IO;int T1;cinT;//memset(sg,-1,sizeof sg);init();while(T--){ll n;cinn;int l1,rsz;while(lr){int midlr11;if(s[mid]n) lmid;else rmid-1;}if(s[l]n) l;if(l1) coutXiaoQiao\n;else coutXiaoHuiHui\n;}// for(int i1;i400;i)// if(dfs(i)) couti: 1endl;// else couti: 0endl;return 0;
}E.石子搬运
O(qn2logn)O(qn^2logn)O(qn2logn) 首先考虑如果没有修改操作不难发现可以设计dp 状态表示f(i,j)f_{(i,j)}f(i,j)表示考虑前iii堆石子搬运jjj次能够搬完 状态转移只需要考虑最后当前这堆石子搬运多少次能够将其搬完
由基本不等式可得对于某一堆石子搬运次数一定的那么均分搬运石子代价一定最小。
如果考虑修改我们用线段树维护对于区间合并直接暴力合并即可O(n2)O(n^2)O(n2) 单点修改时间复杂度n2log(n)n^2log(n)n2log(n)总时间复杂度qn2log(n)qn^2log(n)qn2log(n)
// O(qn^2logn)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N410;
const ll INF0x3f3f3f3f3f3f3f3f;
int n,m,q;
ll a[N];
// ll f[N][N];
struct node
{int l,r;ll f[N];
}tree[N*4];
void pushup(int u)
{for(int i1;im;i) tree[u].f[i]INF;for(int i1;im;i)for(int j1;jm-i;j){if(tree[u1].f[i]INF||tree[u1|1].f[j]INF) continue;tree[u].f[ij]min(tree[u].f[ij],tree[u1].f[i]tree[u1|1].f[j]);}
}
void build(int u,int l,int r)
{tree[u]{l,r};memset(tree[u].f,0x3f,8*N);if(lr){for(int k1;kmin(m,(int)a[l]);k){int xa[l]/k;int pa[l]%k;tree[u].f[k]1ll*(x1)*(x1)*p1ll*x*x*(k-p);}return;}int midlr1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);
}
void modify(int u,int pos,int val)
{if(tree[u].ltree[u].r){for(int k1;kmin(m,val);k){int xval/k;int pval%k;tree[u].f[k]1ll*(x1)*(x1)*p1ll*x*x*(k-p);}return;}int midtree[u].ltree[u].r1;if(posmid) modify(u1,pos,val);else modify(u1|1,pos,val);pushup(u);
}
int main()
{IO;int T1;//cinT;while(T--){cinnm;for(int i1;in;i) cina[i];build(1,1,n);cinq;while(q--){int x,v;cinxv;modify(1,x,v);couttree[1].f[m]\n;}// 尝试没有修改用dp做法是否正确// memset(f,0x3f,sizeof f);// f[0][0]0;// for(int i1;in;i)// for(int j0;jm;j)// for(int k1;kmin(j,(int)a[i]);k)// {// int xa[i]/k;// int pa[i]%k;// ll w1ll*(a[i]/k1)*(a[i]/k1)*pa[i]/k*a[i]/k*(k-p);// f[i][j]min(f[i][j],f[i-1][j-k]w);// }// coutf[n][m]\n;}return 0;
}就会上面几题~~
F-小松鼠吃松果
大佬题解
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includequeue
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
typedef unsigned long long ull;
const int N100010;
int n,m;
int pos[N],h[N];
int hs[N];
struct node
{int t,p,w;bool operator(const nodeo) const{return to.t?po.p:to.t;}
}q[N];
ll tree[N];
int lowbit(int x)
{return x-x;
}
void add(int k,ll x)
{for(;kn;klowbit(k)) tree[k]max(tree[k],x);
}
ll query(int k)
{ll res0;for(;k;k-lowbit(k)) resmax(res,tree[k]);return res;
}
int main()
{IO;int T1;//cinT;while(T--){cinnm;for(int i1;im;i) cinpos[i];for(int i1;im;i) cinh[i];for(int i1;in;i){cinq[i].tq[i].pq[i].w;q[i].th[q[i].p];}for(int i1;in;i){int xq[i].t-pos[q[i].p];int yq[i].tpos[q[i].p];q[i].tx,q[i].py;hs[i]y;}sort(hs1,hs1n);sort(q1,q1n);ll res0;for(int i1;in;i){int klower_bound(hs1,hs1n,q[i].p)-hs;ll dpquery(k)q[i].w;resmax(res,dp);add(k,dp);}coutres\n;}return 0;}要加油哦~
