20191208-题解1
"华为杯"大连理工大学第12届大学生程序设计大赛题解
Problem Designer / Porter : funer, cscyuge, Kinesis, Zeraful, ggwdwsbs
Solution Author: Yzm007, Coca, Kinesis, sher_wu
难度排序：
Easy：ANM
Easy-Middle：HDI
Middle：CK
Middle-Hard：FLBG
Hard：EJ
A. 字符三角形
签到题。
N. 蓝桥杯！爆零！
即统计积最多能被10整除几次，积中出现了几个10。 而10可以被分解成2*5，即统计n个数中共出现了几次2和5，取小即可。
#include<bits/stdc++.h>
using namespace std;
int n,v,two,five;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&v);
for(;v%2==0;v/=2)two++;
for(;v%5==0;v/=5)five++;
}
printf("%d\n",min(two,five));
return 0;
}M. 后缀自动机求回旋字符串
长度为奇显然为NO，考虑长度为偶，此处以长度为8的s串为例。
1 2 3 4 5 6 7 8 若此串合法，需s[1]=s[5]，s[2]=s[6]，…
考虑后挪一位得到新串2 3 4 1，发现仍需满足上式。
因此直接判断即可，可以推广到长度为2*n的情形。
事实上，如将串首尾相接形成一个环，该操作相当于重新选择环的起点，但无论执行多少次操作，当前字母仍应与其相距为n的字母相同。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
bool ok(int n)
{
if(n%2)return 0;
n/=2;
for(int i=0;i<n;++i)
if(s[i]!=s[i+n])return 0;
return 1;
}
int main()
{
scanf("%s",s);
int len=strlen(s);
puts(ok(len)?"YES":"NO");
return 0;
}H. 自定义排序
按题意排序，使用一种\(O(nlogn)\)的排序方式即可通过，或使用STL。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,oa,ob,oc;
struct node
{
int a,b,c;
}e[N];
bool operator<(node x,node y)
{
if(x.a!=y.a)return oa?x.a< y.a:x.a>y.a;
if(x.b!=y.b)return ob?x.b< y.b:x.b>y.b;
if(x.c!=y.c)return oc?x.c< y.c:x.c>y.c;
}
int main()
{
scanf("%d%d%d%d",&n,&oa,&ob,&oc);
for(int i=0;i<n;++i)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
sort(e,e+n);
for(int i=0;i<n;++i)
printf("%d %d %d\n",e[i].a,e[i].b,e[i].c);
return 0;
}D. 爱在公元前
考虑一个月日只可能对应一个年，且9220年02月29日合法，所以先将366个合法日期处理出来。 对于每个询问日期tmp，暴力判断366个日期哪个小于等于tmp即可。
#include<bits/stdc++.h>
using namespace std;
int t,dat[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int cnt,y,m,d;
char s[10];
struct node
{
int y,m,d;
}e[367],tmp;
bool cmp(node a,node b)
{
if(a.y!=b.y)return a.y<b.y;
if(a.m!=b.m)return a.m<b.m;
if(a.d!=b.d)return a.d<b.d;
return 1;
}
bool leap(int x)
{
if(x%400==0||(x%100 && x%4==0))return 1;
return 0;
}
void init()
{
int y;
for(int i=1;i<=12;++i)
{
for(int j=1;j<=31;++j)
{
if(j>dat[i])break;
y=i/10+(i%10)*10+(j/10)*100+(j%10)*1000;
if(!leap(y) && (i==2&&j==29))break;
e[++cnt]=node{y,i,j};
}
}
}
int main()
{
scanf("%d",&t);
init();
while(t--)
{
scanf("%s",s);
y=m=d=0;
for(int i=0;i<4;++i)
y=y*10+(s[i]-'0');
for(int i=4;i<6;++i)
m=m*10+(s[i]-'0');
for(int i=6;i<8;++i)
d=d*10+(s[i]-'0');
tmp=node{y,m,d};
int ans=0;
for(int i=1;i<=cnt;++i)
if(cmp(e[i],tmp))ans++;
printf("%d\n",ans);
}
return 0;
}I. OJ的反作弊系统
按题意二分，二分的位置越界即答案不存在，或使用STL。 小于等于v的最大位置即大于v的最小位置-1。 同理，小于v的最大位置即大于等于v的最小位置-1。
//手写二分
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,v,x[N],pos,ans;
char s[5];
int upper(int l,int r,int v)
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(x[mid]<=v)l=mid+1;
else r=mid-1;
}
return l;
}
int lower(int l,int r,int v)
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(x[mid]<v)l=mid+1;
else r=mid-1;
}
return l;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&x[i]);
sort(x+1,x+n+1);
for(int i=1;i<=m;++i)
{
scanf("%s%d",s,&v);
char op=s[0];
if(op=='A')
{
pos=upper(1,n,v);
if(pos>n)puts("-1");
else printf("%d\n",pos);
}
else if(op=='B')
{
pos=lower(1,n,v);
pos--;
if(pos<1)puts("-1");
else printf("%d\n",pos);
}
else if(op=='C')
{
pos=lower(1,n,v);
if(pos>n)puts("-1");
else printf("%d\n",pos);
}
else if(op=='D')
{
pos=upper(1,n,v);
pos--;
if(pos<1)puts("-1");
else printf("%d\n",pos);
}
}
return 0;
}//STL
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,v,x[N],pos,ans;
char s[5];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&x[i]);
sort(x+1,x+n+1);
for(int i=1;i<=m;++i)
{
scanf("%s%d",s,&v);
char op=s[0];
if(op=='A')
{
pos=upper_bound(x+1,x+n+1,v)-x;
if(pos>n)puts("-1");
else printf("%d\n",pos);
}
else if(op=='B')
{
pos=lower_bound(x+1,x+n+1,v)-x;
pos--;
if(pos<1)puts("-1");
else printf("%d\n",pos);
}
else if(op=='C')
{
pos=lower_bound(x+1,x+n+1,v)-x;
if(pos>n)puts("-1");
else printf("%d\n",pos);
}
else if(op=='D')
{
pos=upper_bound(x+1,x+n+1,v)-x;
pos--;
if(pos<1)puts("-1");
else printf("%d\n",pos);
}
}
return 0;
}C. 耀宗学长的图像处理课本
原题题号UVA297，开始出了\(dep>5\)的数据，向被卡这道题的参赛选手抱歉。 做法较多，可以根据实际矩形递归建树，也可以只利用树形递归建树，先序遍历这棵树。 遇见字母\(p\)就向下递归4个位置，遇到字母\(f\)就统计答案。
#include <cstdio>
#include <cstring>
const int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;
void draw(const char *s, int &p, int r, int c, int w)
{
char ch = s[p++];
if (ch == 'p')
{
draw(s, p, r, c + w / 2, w / 2);
draw(s, p, r, c, w / 2);
draw(s, p, r + w / 2, c, w / 2);
draw(s, p, r + w / 2, c + w / 2, w / 2);
}
else if (ch == 'f')
{
for (int i = r; i < r + w; i++)
for (int j = c; j < c + w; j++)
if (buf[i][j] == 0)
{
buf[i][j] = 1;
cnt++;
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(buf, 0, sizeof(buf));
cnt = 0;
for (int i = 0; i < 2; i++)
{
scanf("%s", s);
int p = 0;
draw(s, p, 0, 0, len);
}
printf("There are %d black pixels.\n", cnt);
}
return 0;
}K. 取模运算
分块，优雅的暴力。
考虑最暴力的回答2询问的方式，\(tong[x]\)代表\(x\)的值的个数，遍历\(x, x+p, x+2p, ...,\)直至上限\({10}^{5}\)，累加\(tong\)的值，所需次数大致为\(\frac{ {10}^{5}}{p}\)。
对于\(p\geq \sqrt{ {10}^{5}}\)的询问，单次所需次数不超过\(\sqrt{ {10}^{5}}\)，可以接受。
对于\(p<\sqrt{ {10}^{5}}\)的询问，暴力显然超时，开二维数组预存所有\(p< \sqrt{ {10}^{5}}\)的答案，now[p][x]代表\(\%p ==x\)的值的个数\((p<\sqrt{ {10}^{5}},x<p )\).
针对每次单点修改，及时更新tong和now数组的值。
针对每次询问，若\(p\geq \sqrt{ {10}^{5}}\)，暴力统计，否则直接回答now[][x]的值。
复杂度为\(O(n\sqrt{n})\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=sqrt(N)+5;
int n,m,op,x,y,a[N],ans;
int now[M][M],tong[N];
int main()
{
scanf("%d%d",&n,&m);
int sq=sqrt(N);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
tong[a[i]]++;
for(int j=1;j<=sq;++j)
now[j][a[i]%j]++;
}
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
for(int j=1;j<=sq;++j)
{
now[j][a[x]%j]--;
now[j][y%j]++;
}
tong[a[x]]--;
tong[y]++;
a[x]=y;
}
else if(op==2)
{
if(x>=y)ans=0;
else
{
if(y<=sq)ans=now[y][x];
else
{
ans=0;
for(int i=x;i<N;i+=y)
ans+=tong[i];
}
}
printf("%d\n",ans);
}
}
return 0;
}F. 菜鸟工程师的分子划分
题意：
平面上有n个点，不是白点就是黑点。现在要放一条直线，使得直线一侧的白点与另一侧的黑点加起来数目最多。直线上的点可以看作位于直线的任意一侧。
思路：
首先假设直线经过两个点，否则可以移动直线使其经过两个点，并且总数不会减少。
所以，我们可以先枚举一个基点，然后以这个点为中心。
围绕基点将其他点按照极角排序，将直线旋转，统计符合要求的点的个数。
需要注意的是，如果将所有的黑点以基点为中心做一个中心对称，则符合要求的点的个数就变成了直线一侧的点的个数。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000 + 5;
struct Point
{
int x, y;
double rad; // with respect to current point
bool operator<(const Point &rhs) const
{
return rad < rhs.rad;
}
} op[maxn], p[maxn];
int n, color[maxn];
// from O-A to O-B, is it a left turn?
bool Left(Point A, Point B)
{
return A.x * B.y - A.y * B.x >= 0;
}
int solve()
{
if(n <= 2)
return 2;
int ans = 0;
// pivot point
for(int i = 0; i < n; i++){
int k = 0;
// the list of other point, sorted in increasing order of rad
for(int j = 0; j < n; j++)
if(j != i){
p[k].x = op[j].x - op[i].x;
p[k].y = op[j].y - op[i].y;
if(color[j]){
p[k].x = -p[k].x;
p[k].y = -p[k].y;
}
p[k].rad = atan2(p[k].y, p[k].x);
k++;
}
sort(p, p+k);
// sweeping. cnt is the number of points whose rad is between p[L] and p[R]
int L = 0, R = 0, cnt = 2;//consider the position of "cnt--"
while(L < k){
if(R == L){
R = (R+1)%k; // empty interval
cnt++;
}
while(R != L && Left(p[L], p[R])){
R = (R+1)%k; // stop when [L,R] spans across > 180 degrees
cnt++;
}
cnt--;
L++;
ans = max(ans, cnt);
}
}
return ans;
}
int main()
{
while(scanf("%d",&n)==1&&n){
for(int i = 0; i < n; i++)
scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);
printf("%d\n", solve());
}
return 0;
}L. 七星堆六朝墓群
求最大同色子矩阵，可采用悬线法或单调栈。h[j]代表当前相同值的高度，L[j]代表以h[j]的高度能移动到的最左位置，R[j]代表以h[j]的高度能移动到的最右位置，则当前枚举的等高子矩阵的面积为\((R[j]-L[j]+1)*h[j]\)。
①单调栈
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
typedef long long ll;
int n,m,a[N][N],h[N],L[N],R[N];
int stk,q[N];
ll ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(a[i][j]==a[i-1][j])h[j]++;
else h[j]=1;
}
int l,r;
for(l=1;l<=n;l=r+1)
{
r=l;
while(r<=n&&a[i][l]==a[i][r])r++;
r--;
stk=0;
for(int k=l;k<=r;++k)
{
while(stk&&h[q[stk]]>=h[k])stk--;
if(!stk)L[k]=l;
else L[k]=q[stk]+1;
q[++stk]=k;
}
stk=0;
for(int k=r;k>=l;--k)
{
while(stk&&h[q[stk]]>=h[k])stk--;
if(!stk)R[k]=r;
else R[k]=q[stk]-1;
q[++stk]=k;
}
for(int k=l;k<=r;++k)
{
ans=max(ans,1ll*(R[k]-L[k]+1)*h[k]*a[i][k]);
}
}
}
printf("%lld\n",ans);
return 0;
}②悬线法
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e3+10;
typedef long long ll;
int m,n,a[N][N];
int l[N],r[N],h[N];
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
}
}
for(int j=1;j<=m;j++)
l[j]=0,r[j]=m+1,h[j]=0;
ll ans=0;
int la,ra;
for(int i=1;i<=n;++i)
{
la=0;ra=m+1;
for(int j=1;j<=m;++j)
{
if(a[i][j]==a[i-1][j])
h[j]++;
else
h[j]=1,l[j]=0,r[j]=m+1;
if(a[i][j]==a[i][j-1])
l[j]=max(l[j],la+1);
else
l[j]=j,la=j-1;
}
for(int j=m;j>=1;--j)
{
if(a[i][j]==a[i][j+1])
r[j]=min(r[j],ra-1);
else
r[j]=j,ra=j+1;
ans=max(ans,1ll*h[j]*(r[j]-l[j]+1)*a[i][j]);
}
}
printf("%lld\n",ans);
}
return 0;
}B. 立方和
线段树经典题目，hdu4578的弱化版本。 首先考虑加与乘。
用add来表示区间内每个数通过加法操作所增加的值(就是说先加a再乘b再加c之后，这里存的数是a*b+c);
用mult来表示区间内每个数被乘以后的倍数（注意默认应当为1）。 然后再考虑立方和，在这里只解释一下平方和怎么维护，立方和原理类似。（代码中的实现为函数up）
例如，我要把区间\([L,R]\)内每个数的值从\(x_i\)变为\(x_i+p\)的话,那么区间内每个数的变化量为\((x_i+p)^2-x_i^2=2x_ip+p^2\),区间平方和\(mk[2]\)的变化量为\(2*mk[1]*p+(R-L+1)*p^2\).那么只需要通过加一个数就可以维护区间平方和了。
需要注意的是，由于这里使用的\(mk[1]\)应当是这段区间发生区间加以前的，因而在更新是应该先更新\(mk[2]\)再更新\(mk[1]\)。
#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e4 + 7;
const int N = 1e5 + 10;
struct node
{
int l, r;
int p[4];
int addlazy, multlazy;
} tree[N << 2];
int a[N];
int mk[4];
void up(int pos, int op)
{
int len = tree[pos].r - tree[pos].l + 1;
if (op == 3)
{
tree[pos].p[3] += 1ll * mk[3] * len % mod + 3ll * mk[2] * tree[pos].p[1] % mod + 3ll * mk[1] * tree[pos].p[2] % mod;
tree[pos].p[3] %= mod;
}
if (op == 2)
{
tree[pos].p[2] += 1ll * mk[2] * len % mod + 2ll * mk[1] * tree[pos].p[1] % mod;
tree[pos].p[2] %= mod;
}
if (op == 1)
{
tree[pos].p[1] += 1ll * mk[1] * len % mod;
tree[pos].p[1] %= mod;
}
}
void pushdown(int pos)
{
if (tree[pos].multlazy != 1)
{
int w = tree[pos].multlazy;
mk[0] = 1;
for (int i = 1; i <= 3; i++)
mk[i] = 1ll * w * mk[i - 1] % mod;
tree[pos * 2].multlazy = 1ll * tree[pos * 2].multlazy * mk[1] % mod;
tree[pos * 2 + 1].multlazy = 1ll * tree[pos * 2 + 1].multlazy * mk[1] % mod;
tree[pos * 2].addlazy = 1ll * tree[pos * 2].addlazy * mk[1] % mod;
tree[pos * 2 + 1].addlazy = 1ll * tree[pos * 2 + 1].addlazy * mk[1] % mod;
for (int i = 1; i <= 3; i++)
{
tree[pos * 2].p[i] = 1ll * tree[pos * 2].p[i] * mk[i] % mod;
tree[pos * 2 + 1].p[i] = 1ll * tree[pos * 2 + 1].p[i] * mk[i] % mod;
}
tree[pos].multlazy = 1;
}
if (tree[pos].addlazy != 0)
{
int w = tree[pos].addlazy;
mk[0] = 1;
for (int i = 1; i <= 3; i++)
mk[i] = 1ll * w * mk[i - 1] % mod;
tree[pos * 2].addlazy += w, tree[pos * 2].addlazy %= mod;
tree[pos * 2 + 1].addlazy += w, tree[pos * 2 + 1].addlazy %= mod;
up(pos * 2, 3);
up(pos * 2 + 1, 3);
up(pos * 2, 2);
up(pos * 2 + 1, 2);
up(pos * 2, 1);
up(pos * 2 + 1, 1);
tree[pos].addlazy = 0;
}
}
void pushup(int pos)
{
for (int i = 1; i <= 3; i++)
tree[pos].p[i] = (tree[pos * 2 + 1].p[i] + tree[pos * 2].p[i]) % mod;
}
void build(int pos, int l, int r)
{
tree[pos].l = l;
tree[pos].r = r;
tree[pos].multlazy = 1;
if (l == r)
{
tree[pos].p[1] = a[l] % mod;
tree[pos].p[2] = a[l] * a[l] % mod;
tree[pos].p[3] = 1ll * a[l] * a[l] * a[l] % mod;
return;
}
int mid = (tree[pos].l + tree[pos].r) >> 1;
build(pos * 2, l, mid);
build(pos * 2 + 1, mid + 1, r);
pushup(pos);
}
void update(int pos, int l, int r, int w, int op)
{
if (l <= tree[pos].l && tree[pos].r <= r)
{
mk[0] = 1;
for (int i = 1; i <= 3; i++)
mk[i] = 1ll * w * mk[i - 1] % mod;
if (op == 1)
{
tree[pos].addlazy += w;
tree[pos].addlazy %= mod;
up(pos, 3);
up(pos, 2);
up(pos, 1);
}
else
{
tree[pos].multlazy = 1ll * w * tree[pos].multlazy % mod;
tree[pos].addlazy = 1ll * w * tree[pos].addlazy % mod;
for (int i = 1; i <= 3; i++)
tree[pos].p[i] = 1ll * tree[pos].p[i] * mk[i] % mod;
}
return;
}
pushdown(pos);
int mid = (tree[pos].l + tree[pos].r) >> 1;
if (l <= mid)
update(pos * 2, l, r, w, op);
if (r > mid)
update(pos * 2 + 1, l, r, w, op);
pushup(pos);
}
int quary(int pos, int l, int r)
{
if (l <= tree[pos].l && tree[pos].r <= r)
{
return tree[pos].p[3] % mod;
}
pushdown(pos);
int mid = (tree[pos].l + tree[pos].r) >> 1;
int res = 0;
if (l <= mid)
res += quary(pos * 2, l, r);
res %= mod;
if (r > mid)
res += quary(pos * 2 + 1, l, r);
return res % mod;
}
int n, m;
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("r.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
//cout<<tree[1].p[1]<<endl;
for (int i = 1; i <= m; i++)
{
int ff, x, y, w;
scanf("%d%d%d", &ff, &x, &y);
if (ff == 1)
{
scanf("%d", &w);
update(1, x, y, w, 1);
}
else if (ff == 2)
{
scanf("%d", &w);
update(1, x, y, w, 2);
}
else
{
printf("%d\n", quary(1, x, y));
}
}
}G. 牙签自动机
①暴力
把一根木棍分为4等分，然后在1/4与3/4的位置做标记，表示这里有一根木棍。然后每次判断标记点的边上能不能放一根木棍。奇数轮，只能横着摆；偶数轮，只能竖着摆。比如在判断\([i,j]\)点的左侧能不能摆棒子的时候，判断\([i-1,j-1],[i-1,j+1],[i-2,j]\)是否被标记（多判一个点的原因是，注意第三轮，两根横棒中间没有生成竖棒），如果都没有，那么可以在\([i-1,j-2]\)~\([i-1,j+2]\)间摆一根棒子，并标记\([i-1,j-1],[i-1,j+1]\).
例如，开始的一根摆在了\([1998,2000]\)~\([2002,2000]\)，然后标记\([1999,2000],[2001,2000]\),判断\([1998,1999],[1998,2001],[1997,2000]\)都没有被标记，那么可以在左边放竖棒，并标记\([1998,1999],[1998,2001]\). 程序中使用了队列来确定这到底是第几轮。
#include<bits/stdc++.h>
using namespace std;
int ans[1050],mp[4000][4000];
queue<pair<int,int> > q;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
inline void init()
{
int p=0,num=1,tot=1;
ans[1]=1;
mp[1999][2000]=1;
mp[2001][2000]=1;
q.push(make_pair<int,int>(1999,2000));
q.push(make_pair<int,int>(2001,2000));
q.push(make_pair<int,int>(0,0));
while(num<1030)
{
++num;
while(1)
{
int le=q.front().first,ri=q.front().second;
q.pop();
if(le==0&&ri==0) break;
if(!p&&!mp[le-1][ri-1]&&!mp[le-1][ri+1]&&!mp[le-2][ri])
{
++tot;
mp[le-1][ri-1]=mp[le-1][ri+1]=1;
q.push(make_pair<int,int>(le-1,ri-1));
q.push(make_pair<int,int>(le-1,ri+1));
continue;
}
if(!p&&!mp[le+1][ri-1]&&!mp[le+1][ri+1]&&!mp[le+2][ri])
{
++tot;
mp[le+1][ri-1]=mp[le+1][ri+1]=1;
q.push(make_pair<int,int>(le+1,ri-1));
q.push(make_pair<int,int>(le+1,ri+1));
continue;
}
if(p&&!mp[le-1][ri-1]&&!mp[le+1][ri-1]&&!mp[le][ri-2])
{
++tot;
mp[le-1][ri-1]=mp[le+1][ri-1]=1;
q.push(make_pair<int,int>(le-1,ri-1));
q.push(make_pair<int,int>(le+1,ri-1));
continue;
}
if(p&&!mp[le-1][ri+1]&&!mp[le+1][ri+1]&&!mp[le][ri+2])
{
++tot;
mp[le-1][ri+1]=mp[le+1][ri+1]=1;
q.push(make_pair<int,int>(le-1,ri+1));
q.push(make_pair<int,int>(le+1,ri+1));
continue;
}
}
ans[num]=tot;
q.push(make_pair<int,int>(0,0));
p^=1;
}
}
int main(){
init();
int n=read();
while(n--)
{
int now=read();
printf("%d%c",ans[now],n?' ':'\n');
}
}②本地模拟直接交打表后的值
将打表后的值放入mp[1030]，每次直接查询mp[i].代码仅11MB
③找规律
我们针对每个图形的右上角进行分析可以发现：每一次非2的次方的数字时，右上角模块总可以被划分成三个部分，即sto[m]*2和sto[m+1]；同时，每一次为2的次方的时候，整个图形为一个外边封闭近似正方形，其内部为\(2^{2*k+1}+1\)个牙签。
因此，图形的表达式为： \[\left\{\begin{matrix} n=2^k & sto[n] = 2^{(2k+1)}/3\\ n\neq 2^k & sto[n] = 2^{k} + sto[n - 2^{k}] * 2 + sto[n - 2^{k}+1] -1 \end{matrix}\right.\]
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll sto[1025], base[35] = {1ll};
inline ll read()
{
ll X = 0, w = 0;
char ch = 0;
while (!isdigit(ch))
{
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch))
X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline void write(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline void writesp(int x)
{
write(x);
putchar(' ');
}
int main()
{
for (int i = 1; i <= 30; i++)
base[i] = base[i - 1] << 1ll;
for (int i = 0; i <= 1024; i++)
{
int k = lower_bound(base, base + 15, i) - base;
if (base[k] == i)
sto[i] = (base[2 * k + 1] + 1) / 3;
else
{
k--;
int m = i - base[k];
sto[i] = sto[base[k]] + 2ll * sto[m] + sto[m + 1] - 1ll;
}
}
sto[0] = 0;
int T = read();
for (int i = 0; i < T; i++)
{
if (i)
putchar(' ');
write(sto[read()]);
}
return 0;
}E. 膜法项链 Easy Version
\(n\leq2000\)
从0到n-1枚举第二种操作的使用次数step，
那么对于最终得到的编号为i的珍珠，
假如它是召放在j位置然后右移多次得到的，
则一定有 \(i-step\leq j \leq i\) ，
并且这是充要的，即它可以由这个区间的任何一个j生成后右移多次得到。
因此只用这个区间的a[j]的最小值就是得到i的代价。
把所有i的代价相加再加上step*x就是step对应的最小代价。
注意，这个题目是一个环而不是链，这只需要将a复制一份即可。
求区间最小值有很多方法，比如单调队列。
时间复杂度 \(O(n^2)\)
戳我补题
E. 膜法项链 Hard Version
时间复杂度\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
int n;long long w;
long long d[2000100];
long long a[2000100];
long long st[2000200];
int num[2000200];
int se=0;
int main(){
scanf("%d%lld",&n,&w);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
a[i+n]=a[i];
}
a[2*n]=-1;
for(int i=0;i<=2*n;i++){
if(se==0||st[se-1]<=a[i]){
st[se]=a[i];
num[se]=i;
se++;
}
else{
while(se&&st[se-1]>a[i]){
if(i>n){
int d2begin=max(num[se-1],n);
int d2len=i-d2begin;
int dbegin;int dlen;
if(se==1){
dbegin=0;
}
else{
dbegin=num[se-2];
}
dlen=num[se-1]-dbegin;
d[d2begin-num[se-1]]+=st[se-1];d[d2begin-num[se-1]+d2len]-=st[se-1];
d[d2begin-num[se-1]+dlen]-=st[se-1];d[d2begin-num[se-1]+dlen+d2len]+=st[se-1];
}
se--;
}
st[se]=a[i];
num[se]=i;
se++;
}
}
for(int i=1;i<=2*n;i++){
d[i]=d[i-1]+d[i];
}
for(int i=1;i<=2*n;i++){
d[i]=d[i-1]+d[i];
}
long long ans=0x3f3f3f3f3f3f3f3f;
for(int i=0;i<n;i++){
ans=min(ans,i*w+d[i]);
}
printf("%lld\n",ans);
}J. 更强的未来道具FG-C193 Easy Version
以每个为止判断每个对称轴会对称到哪一个位置。最后查看所有位置是否相同。
复杂度\(O(n^2)\)
戳我补题
J. 更强的未来道具FG-C193 Hard Version
像manacher一样两字符中间补一个字符。然后对manacher判断的位置进行判断，不过把判断两字符是否相同改为将带权并查集合并。 复杂度\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
int a[200040];
int abc[220000];
int abcpos[220000];
int fa[200040];
int ans[200040];
int unans[200020];
int aans[100020];
int find(int i){
if(fa[i]!=i){
fa[i]=find(fa[i]);
ans[i]=ans[fa[i]];
return fa[i];
}
return fa[i];
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<2*n;i++){
scanf("%d",&a[i]);
a[i]*=2;
}
for(int i=0;i<=2*n;i++){
fa[i]=i;
}
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
int tmp;
scanf("%d",&tmp);
char tchar;
scanf(" %c",&tchar);
if(aans[tmp]&&aans[tmp]!=tchar){
printf("-1\n");return 0;
}
aans[tmp]=tchar;
if(abc[tchar]!=0){
find(2*tmp);
find(abcpos[tchar]);
fa[find(2*tmp)]=find(abcpos[tchar]);
}
ans[2*tmp]=tchar;
abc[tchar]++;abcpos[tchar]=tmp*2;
}
for(int i=1;i<=n;i++){
fa[i*2-1]=1;
ans[i*2-1]=257;
}
int nowmax=0;
for(int i=0;i<2*n;i++){
while(nowmax<=a[i]+i-1){
if(nowmax<2*n&&(i-nowmax+i)>=0){
if(find(i-nowmax+i)!=find(nowmax)){
if(ans[find(i-nowmax+i)]&&ans[find(nowmax)]&&ans[find(i-nowmax+i)]!=ans[find(nowmax)]){
printf("-1\n"); return 0;
}
else{
if(ans[find(nowmax)]==0) {
fa[find(nowmax)]=find(i-nowmax+i);find(nowmax);
}
else{
fa[find(i-nowmax+i)]=find(nowmax);
find(i-nowmax+i);
}
}
}
}
nowmax++;
}
}
for(int i=0;i<2*n;i++){
if(i+a[i]<2*n&&i-a[i]>=0&&(i-a[i])%2==0){
if(find(i-a[i])==find(i+a[i])){
printf("-1\n"); return 0;
}
}
if(i+a[i]+1<2*n&&i-a[i]-1>=0&&(i-a[i])%2!=0){
if(find(i-a[i]-1)==find(i+a[i]+1)){
printf("-1\n"); return 0;
}
}
}
int unknow=0;
for(int i=0;i<n;i++){
if(ans[find(2*i)]==0){
unans[unknow]=i;
unknow++;
}
}
if(unknow){
for(int i=0;i<unknow;i++){
if(i!=0) printf(" ");
printf("%d",unans[i]);
}
printf("\n");
}
else{
for(int i=0;i<n;i++){
printf("%c",ans[find(2*i)]);
}
printf("\n");
}
}