D E统统FST...
差一点就飞升了...
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
A.King of Thieves
给你一张地图，让你从某个*开始跳等步长的四次。如果均在*则输出yes，否则输出no
枚举起始点和步长直接做就可以了
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
B.Om Nom and Dark Park
给你一棵满二叉树。每条边上有路灯。要求从根走到叶子节点经过的路灯数相同。问最少添加几盏路灯
这题我们可以递归处理。每次让两棵子树的路径灯数相同就可以了
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
C.Om Nom and Candies
有两种糖。质量分别为wr,wb。快乐度分别为hr,hb
你只能吃总质量不超过c的糖，问你最多可以获得多少快乐的
【absi:这题不就是乱搞么】
首先看到数据范围。我们可以想到肯定要多选h/w大的那一个。那么就可以贪心选把c缩小很多
然后缩到多小呢。缩小到wr*wb就可以了
然后我们枚举wr和wb中大的那一个。更新ans即可
最后枚举部分的复杂度是sqrt(c)所以完全无压力
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
D.Om Nom and Necklace
给你一个字符串，要你输出从1到i可否表示成k个AB+一个A的形式。1到n均有询问
我们可以枚举AB的长度，然后倍增判断是否可以复制n段。最后那个A直接hash和开头比较就可以了。二分A的长度看看最长是多少然后那一段都+1即可
也可以用KMP的next数组辅助判定（如下面那段Loriex的程序）
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
E.Transmitting Levels
给你一个环，q个询问。每次询问把环分成不超过bi的若干段【若单个数大于bi则这个数可以单独一段】。问最少可以分成几段
先把整个数组复制到后面一遍断环。每次处理next[i]表示从i开始最远延伸到next[i]使得这段不超过bi。扫一遍即可求出
然后从n到1扫一遍。fx表示需要多少段，fl表示最后一段延伸到哪里。fx[i]=fx[next[i]]+1 fl[next[i]]=max(fl[next[i]],next[i])
然后枚举起点。在判断一下终止节点是否在起点前面然后把ans加1或者不加就可以了
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
code:
A.King of Thieves
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1001];
int main()
{
int n;
scanf("%d",&n);
string x;
cin>>x;
int i;
for(i=1;i<=n;i++)
{
if(x[i-1]=='.')
a[i]=0;
else
a[i]=1;
}
int j,k;
for(i=1;i<=n;i++)
{
int s;
int d=i;
if(a[i]==0)
continue;
for(j=1;j<=n;j++)
{
d=i;
s=1;
for(k=1;k<=4;k++)
{
if(d+j>n)
break;
if(a[d+j]==0)
break;
else
s++;
d+=j;
}
if(s==5)
{
printf("yes\n");
return 0;
}
}
}
printf("no\n");
return 0;
}
B.Om Nom and Dark Park
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct line
{
int s,t;
int x;
int next;
}a[100001];
int head[100001];
int edge;
inline void add(int s,int t,int x)
{
a[edge].next=head[s];
head[s]=edge;
a[edge].s=s;
a[edge].t=t;
a[edge].x=x;
}
bool v[100001];
int fx[100001];
int ans=0;
inline int absx(int x)
{
if(x<0)
x=-x;
return x;
}
inline void dfs(int d)
{
v[d]=true;
int i;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
if(!v[t])
{
dfs(t);
}
}
int s=0,s1=0,s2=0;
for(i=head[d];i!=0;i=a[i].next)
{
int t=a[i].t;
if(t!=d/2)
{
if(s==0)
{
s++;
s1=a[i].x;
}
else
s2=a[i].x;
}
}
ans+=absx(s2+fx[d*2]-(s1+fx[d*2+1]));
fx[d]+=max(s2+fx[d*2],s1+fx[d*2+1]);
}
int main()
{
int n;
scanf("%d",&n);
int i,j;
int s=0;
int d=1;
int x;
for(i=1;i<=n;i++)
{
for(j=1;j<=1<<i;j++)
{
scanf("%d",&x);
if(s==0)
{
s++;
edge++;
add(d,d*2,x);
edge++;
add(d*2,d,x);
}
else
{
s=0;
edge++;
add(d,d*2+1,x);
edge++;
add(d*2+1,d,x);
d++;
}
}
}
dfs(1);
printf("%d\n",ans);
return 0;
}
C.Om Nom and Candies
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long c,hr,hb,wr,wb;
long long ans=0;
inline void prepare()
{
if((long long)2*wb*wr<=c)
{
long long t=wb*wr;
long long t2=c/t-2;
c=c%t+t+t;
if(wb*hr>wr*hb)
ans+=hr*wb*t2;
else
ans+=hb*wr*t2;
}
}
int main()
{
scanf("%I64d%I64d%I64d%I64d%I64d",&c,&hr,&hb,&wr,&wb);
if(wr>wb)
{
long long t=wr;
wr=wb;
wb=t;
t=hr;
hr=hb;
hb=t;
}
prepare();
long long i;
long long ansx=0;
for(i=0;i<=c/wb;i++)
ansx=max(ansx,ans+(c-i*wb)/wr*hr+i*hb);
printf("%I64d\n",ansx);
return 0;
}
D.Om Nom and Necklace
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
using namespace std;
#define N 1001111
#define mod1 1000000007
#define mod2 1000000009
typedef long long LL;
int geti() {
static int res;
static char pp;
pp = getchar();
while (pp < '0' || pp > '9')
pp = getchar();
res = 0;
while (pp <= '9' && pp >= '0')
res = res * 10 - '0' + pp, pp = getchar();
return res;
}
int n, K, Next[N], tr[N], sr[N];
bool ok[N];
char p[N];
void kmp() {
for (int i = 2; i <= n; i++) {
int c = Next[i-1];
while (c && p[c+1] != p[i])
c = Next[c];
if (!c)
Next[i] = p[1]==p[i];
else
Next[i] = c + 1;
}
}
LL power(LL a, int b) {
LL res = 1;
int c = b + 2;
while (b) {
if (b & 1) res = res * a % c;
b >>= 1;
a = a * a % c;
}
return res;
}
LL Hash1[N], Hash2[N], pow1[N], pow2[N];
LL Ha1(int l, int r) {
return (Hash1[r] - Hash1[l-1]*pow1[r-l+1]%mod1 + mod1) % mod1;
}
LL Ha2(int l, int r) {
return (Hash2[r] - Hash2[l-1]*pow2[r-l+1]%mod2 + mod2) % mod2;
}
int fr(int bg, int ls) {
if (Ha1(bg + 1, bg + ls) == Hash1[ls] && Ha2(bg + 1, bg + ls) == Hash2[ls])
return ls + 1;
int l = 0, r = ls;
while (l != r) {
int mid = l + r >> 1;
if (Ha1(bg + 1, bg + mid) == Hash1[mid] && Ha2(bg + 1, bg + mid) == Hash2[mid])
l = mid + 1;
else
r = mid;
}
return l;
}
void pre() {
Hash1[1] = Hash2[1] = p[1];
pow1[1] = 3311;
pow2[1] = 3311;
pow1[0] = pow2[0] = 1;
for (int i = 2; i <= n; i++) {
Hash1[i] = (Hash1[i-1] * 3311 + p[i]) % mod1;
Hash2[i] = (Hash2[i-1] * 3311 + p[i]) % mod2;
pow1[i] = pow1[i-1] * 3311 % mod1;
pow2[i] = pow2[i-1] * 3311 % mod2;
}
}
int rc[N];
int main() {
scanf("%d%d", &n, &K);
if (K == 1) {
for (int i = 1; i <= n; i++)
printf("1");
printf("\n");
return 0;
}
scanf("%s", p + 1);
pre();
kmp();
for (int i = 1; i <= n; i++) {
sr[i] = i - Next[i];
tr[i] = i % sr[i] == 0 ? i / sr[i] : 1;
}
for (int i = 1; i * K <= n; i++) {
if (tr[i*K] % K == 0) {
int r = fr(i * K, i);
rc[i * K]++;
rc[i * K + r]--;
}
}
for (int i = 1; i <= n; i++)
rc[i] += rc[i-1];
for (int i = 1; i <= n; i++)
printf("%d", rc[i] > 0 ? 1 : 0);
printf("\n");
return 0;
}
E.Transmitting Levels
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long a[3000001],que[3000001];
long long b[3000001];
int next[3000001],fx[3000001],fl[3000001];
int main()
{
int n,q;
scanf("%d%d",&n,&q);
int i,j;
for(i=1;i<=n;i++)
scanf("%I64d",&a[i]);
for(i=n+1;i<=2*n;i++)
a[i]=a[i-n];
long long x;
long long sum;
for(i=1;i<=q;i++)
{
memset(next,0,sizeof(next));
memset(fx,0,sizeof(fx));
memset(fl,0,sizeof(fl));
scanf("%I64d",&b[i]);
sum=0;
int l=0,r=1;
l++;
que[r]=a[1];
sum+=a[1];
for(j=2;j<=n*2;j++)
{
sum+=a[j];
r++;
que[r]=a[j];
while(sum>b[i])
{
next[l]=r-1;
sum-=a[l];
l++;
}
}
while(l!=r)
{
next[l]=n*2;
l++;
}
for(j=n;j>=1;j--)
{
fx[j]=fx[next[j]+1]+1;
fl[j]=max(fl[next[j]+1],next[j]);
}
int ans=2100000000;
for(j=1;j<=n;j++)
{
int xt=fx[j];
if(fl[j]-n<j-1&&next[fl[j]-n]>=j-1)
xt++;
else if(next[fl[j]-n]<j-1)
continue;
ans=min(xt,ans);
}
printf("%d\n",ans);
}
}
