2018-07-11
[NOIP模拟赛]
[测评环境：windows]
[hzq84621]
除草
文件名： weed
题目类型： 传统题
时间限制： 1秒
内存限制： 128MB
编译优化： 无
题目描述
小A有一块三角形的草坪。
小A还有一个圆形的除草机，把它放在草坪里就可以对一整个圆形区域就行除草。
但是由于草坪边界有栅栏，除草机并不能做到对整个草坪做到除草，因为除草机不能越过栅栏。
如果无法理解可以看一下目录下的png文件。
为了防止精度误差，你需要输出的是能够除草的面积/总草坪面积
输入格式
四个正整数，前三个正整数描述三角形三边长度，最后一个正整数描述除草机半径。
输出格式
共一个实数表示能够除草的区域的面积，你的答案和实际答案误差不超过0.000001即认为正确。
样例输入
3 4 5 1
样例输出
0.5235987755982
数据规模与约定
对于50%的数据满足给出的是一个直角三角形
对于100%的数据， 输入的所有数字不超过10000
出题人的关怀
海伦公式：
定义p=(a+b+c)/2
三角形面积S=\sqrt{p(p-a)(p-b)(p-c)}
显然怎么样做都行，无非是麻不麻烦和精度怎么样。
这里给一种比较简单的做法。
不难发现当r变化时不能被够到的部分其实是形状相同大小不同的，也就是相似的。
那么我们不妨算出内接圆情况的答案，然后按照r和内接圆半径的比例缩放即可。
/*#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double pi=3.1415926535897932384626433832795,eps=0.0000001;
int main()
{
int a,b,c,r,mx,l1,l2;
scanf("%d%d%d%d",&a,&b,&c,&r);
if(a>b&&a>c){
mx=a;l1=b;l2=c;
}
else if(b>a&&b>c){
mx=b;l1=a;l2=c;
}
else if(c>b&&c>a){
mx=c;l1=a;l2=b;
}
// cout<<mx<<" "<<b<<" "<<c<<endl;
double p=(double)(a+b+c)/2;
double s=sqrt(p*(p-a)*(p-b)*(p-c));
double yuan=(double)r*r*pi;
if(mx*mx==l1*l1+l2*l2)
{
// cout<<(l1+l2-mx)/2<<endl;
if(r<=(l1+l2-mx)/2){
// double tri=(double)l1*l2*1.0/2;
printf("%.15lf",yuan/s);
}
else puts("0");
return 0;
}
double rr=s*2/(a+b+c);
if(r<=rr+eps)
{
printf("%.15lf",yuan/s);
return 0;
}
else puts("0");
}//除草机是可以移动的!还以为真的那么简单。。。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double pi=3.1415926535897932384626433832795;
int main()
{
freopen("weed.in","r",stdin);
freopen("weed.out","w",stdout);
double a,b,c,r,mx,l1,l2;
scanf("%lf%lf%lf%lf",&a,&b,&c,&r);
double p=(double)(a+b+c)/2;
double s=sqrt(p*(p-a)*(p-b)*(p-c));
double yuan=(double)r*r*pi;
double aa=asin(2*s/b/c),bb=asin(2*s/a/c);
// cout<<2*s/b/c<<" "<<s<<endl;
// cout<<aa<<" "<<bb<<endl;
double x1=1.0*r/tan(aa/2),x2=1.0*r/tan(bb/2);
double xx=x1+x2;
// cout<<xx<<endl;
double ss=s*xx*xx/c/c;
// cout<<ss<<endl;
// cout<<yuan<<endl;
printf("%.15lf",1.0*(s-ss+yuan)/s);
}精度爆炸
*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double pi=3.1415926535897932384626433832795;
int main()
{
freopen("weed.in","r",stdin);
freopen("weed.out","w",stdout);
double a,b,c,r,mx,l1,l2;
scanf("%lf%lf%lf%lf",&a,&b,&c,&r);
double p=(double)(a+b+c)/2;
double s=sqrt(p*(p-a)*(p-b)*(p-c));
double yuan=(double)r*r*pi;
double R=s/p;//内切圆半径
// double aa=asin(2*s/b/c),bb=asin(2*s/a/c);
// cout<<2*s/b/c<<" "<<s<<endl;
// cout<<aa<<" "<<bb<<endl;
// double x1=1.0*r/tan(aa/2),x2=1.0*r/tan(bb/2);
// double xx=x1+x2;
// cout<<xx<<endl;
double ss=s*r*r/R/R;//考场上居然没想到用圆半径相似。。被初二小学妹吊打。。。
// cout<<ss<<endl;
// cout<<yuan<<endl;
printf("%.15lf",1.0*(s-ss+yuan)/s);
}
跳棋
文件名： chess
题目类型： 传统题
时间限制： 1秒
内存限制： 128MB
编译优化： 无
题目描述
小A是跳棋大师。
跳棋的规则是，一颗棋子可以移动一个单位，或者移动越过一个另一个棋子运动一个单位。
小A在一条数轴上放了n颗棋子，第i颗棋子位于a_{i}的位置，然后给了每个棋子一个编号。
现在小A想要知道，所有跳棋到达0的可能顺序有多少种。
出于某些模因污染，小A只会向左移动跳棋。
输入格式
第一行一个整数n
接下来一行n个整数描述a_{i}
保证a_{i}
输出格式
一个整数，表示可能的方案数,mod 1000000007后输出
样例输入
3
1 2 3
样例输出
4
样例解释
3不能同时越过1和2，所以可行的顺序有123,132,231,213
数据规模与约定
对于30%的数据，满足n≤8
对于60%的数据，满足a_{i}>=a_{i+1}-2
另存在10%数据满足a_{i}=i
对于100%的数据，满足n≤1000000,0
考虑一个比较简单的情况：
1、3、5、7、9...
这种时候答案显然是n!因为我们可以让任意一个棋子在其他棋子不移动的情况下成为下一个到达的棋子。
也不难证明这是最“劣”的能够有n!种方案的情况。
棋子与棋子除了编号并没有不同，换而言之一个棋子离开之后后面的棋子如果能够到达他的位置就可以顶替他。
首先把所有棋子都尽可能向左靠，因为越向左靠对后面的棋子来说有更多的调整空间。
比如1 5 6 7，往左靠就可以得到1 3 5 7的情况。
当某个位置不得不出现相邻两颗棋子距离为1的情况时，比如1、3、4，此时能够作为下一个到达的棋子就只有前面三颗，因为后面的棋子不能同时越过相邻的两颗。
然后考虑一颗棋子离开了会怎样，无论是哪颗棋子离开了，第三颗都可以到达他的位置，无论是谁离开，最后都可以到达1、3这个“较优”的状态。
所以这样模拟一遍就好了。注意最后的边界状况。
自己粗糙的理解
一颗棋子移动了并不一定要直接移去终点！！！
所以把所有棋子向左移之后是等价的
然后就会有相差二或者相邻
两个棋子相邻则后面的棋子无法移动故下一步只能移动之前的棋子，而每一种又是等价的，直接把一个棋子送去终点其他棋子隔一排布
相差一的序列答案显然是len!
/*#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
#define put putchar('\n')
using namespace std;
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}
inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}
const int mod=1000000007;
int mx,n,ans,a[10000],v[10000],s[10000];
bool vis[10000000],t[1000000];
bool check()
{
// memset(vis,0,sizeof vis);
// for(int i=1;i<=n;i++)cout<<s[i]<<" ";puts("");
for(int i=1;i<=n;i++)
{
vis[0]=0;
if(vis[a[s[i]]-1]&&vis[a[s[i]]-2])return 0;
if(!vis[a[s[i]]-1]){
vis[a[s[i]]-1]=1;
vis[a[s[i]]]=0;
}
else if(vis[a[s[i]]-1]==1&&vis[a[s[i]]-2]==0){
vis[a[s[i]]-2]=1;
vis[a[s[i]]]=0;
}
// for(int i=1;i<=n;i++)cout<<vis[i];puts("");
}
return 1;
}
void dfs(int rt)
{
if(rt>n){
for(int i=1;i<=mx;i++)t[i]=vis[i];
if(check()){
ans=(ans+1)%mod;
// for(int i=1;i<=n;i++)cout<<s[i]<<" ";puts("");
}
for(int i=1;i<=mx;i++)vis[i]=t[i];
return;
}
for(int i=1;i<=n;i++)
{
if(!v[i]){
v[i]=1;
s[rt]=i;
dfs(rt+1);
v[i]=0;
}
}
}
signed main()
{
// int n;
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
int ff=1;
n=read();
for(int i=1;i<=n;i++){
a[i]=read(),vis[a[i]]=1,mx=max(a[i],mx);if(a[i]<a[i-1]+2&&i!=1)ff=0;
}
if(ff=1){
long long k=1;
for(int i=1;i<=n;i++)
k=k*i%mod;
printf("%lld",k);
return 0;
}
dfs(1);
printf("%lld",ans%mod);
}*/
#include <iostream>
#include <cstdio>
#define int long long
#define put putchar('\n')
using namespace std;
const int mod=1000000007;
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}
inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}
int a[1000000];
signed main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
int n,ans=1;
n=read();
int now=n; a[0]=-1;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)
{
a[i]=min(a[i],a[i-1]+2);//左移
if(a[i]==a[i-1]+1){//两个相邻 下一步只能选前面的
ans=(ans*(i+now-n)%mod);
now--;//棋子个数减少
a[i]--;//i替代i-1
}
}
for(int i=now;i>=1;i--)ans=(ans*i)%mod;//剩下的数都不相邻，方案数为now!
printf("%d",ans);
}
聚变
文件名： fusion
题目类型： 传统题
时间限制： 1秒
内存限制： 256MB
编译优化： 无
题目描述
知名科学家小A在2118年在计算机上实现了模拟聚变的过程。
我们将她研究的过程简化。
核子共有26种，可以用a到z共26个字母表示。
核子聚变的过程可以用一个字符串描述。
按照顺序从左到右的顺序，假如有两个相同核子相邻，两个核子就会相互吸引发生聚变生成一个序号+1的核子，特殊的，两个z核子相邻会湮灭没有新的核子生成。
每当两个核子聚变时，就需要重新从左到右重复找到两个相邻的相同核子直到不存在为止。
比如zyzzy->zyy->zz->
小A为了做出足够有效的实验，每次会从一个字符串中选定一个子串操作。
她想要知道每次实验这个子串中的核子能否最终全部湮灭。
输入格式
第一行一个只有小写字母的字符串。
第二行一个数n表示询问次数
接下来n行每行两个正整数l_{i},r_{i}表示询问区间
输出格式
对每次询问输出一行Yes或No表示答案
样例输入
yzyyyzyzyyyz
8
1 6
7 12
1 12
6 11
1 1
1 3
4 9
3 8
样例输出
Yes
Yes
Yes
Yes
No
No
No
No
数据规模与约定
L表示字符串长度
对于30%的数据满足L<=100
对于60%的数据满足L<=3000,n<=3000
另存在20%数据满足字符串中只存在y,z
对于100%的数据,L<=500000,n<=1000000
倍增裸题。
60p送你
10p因为只有y,z所以一段区间处理之后一定只有y,yz,zy,z,空五种情况，所以可以数据结构维护每个区间以这5种情况为开头分别会是什么结果。
剩下30，直接倍增就行了。
难点在于状态过多无法有效记录，所以按照字符串位数倍增显然不行。
那就按照结果倍增。
dp_{i,j}表示从第i个位置开始操作，最小的满足从i到dp_{i,j}的操作结果为一个字符j的位置。
显然可以倍增。
但是这样还不够，可能会出现很多次全都消完的情况，直接跑会退化成nL
Dp_{i,j}表示从第i个位置开始操作，第2^j次出现全部消完时的位置
然后就是通过倍增判断l能否通过Dp_{i,j}跳到r了
/*#include <iostream>
#include <cstdio>
using namespace std;
int n;
char a[100000],t[10000],tmp[10000];
int main()
{
int ans=1,ln;
scanf("%d",&ln);
scanf("%s",t+1);
while(ln>1)
{
int flag=0,len=0;
for(int i=1;i<=ln;i++)
{
int f=0;
if(t[i]==t[i+1]){
flag=1;
if(t[i]=='z')f=1;
else tmp[++len]=char(t[i]+1),f=1;//,cout<<t[i+1]<<" "<<tmp[len]<<endl;
// cout<<t[i]<<" "<<t[i+1]<<endl;
}
else tmp[++len]=t[i],cout<<t[i];
if(f)i++;
// cout<<i<<" ";
}
puts("");
cout<<len;for(int i=1;i<=len;i++)cout<<tmp[i];puts("");
for(int i=1;i<=len;i++)t[i]=tmp[i];//,cout<<t[i];puts("");
ln=len+1;
if(flag==0){
ans=0;break;
}
}
if(ans)puts("Yes");
else puts("No");
}*/
/*
5
yzyyz
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n;
char a[1000005];
int nxt[1000005][22],nt[1000005][27];
//nt i j表示从第i位开始最近的消完之后只剩j后的位置
//nxt i j表示从第i位开始消掉2^i个独立的区间后的位置
void pre()
{
for(int i=1;i<=n+2;i++)
for(int j=0;j<=26;j++)nxt[i][j]=nt[i][j]=n+2;//控制边界
for(int i=n;i>=1;i--){//倒着枚举以便写最后一句话
nt[i][a[i]]=i+1;
for(int j=a[i]+1;j<=26;j++) nt[i][j]=nt[nt[i][j-1]][j-1];//可以理解为合并
nxt[i][0]=nt[i][26];
for(int j=1;j<=20;j++) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
for(int j=0;j<26;j++) if(nt[i][j]==n+2) nt[i][j]=nt[nxt[i][0]][j];//防止类似azza......之类的情况 因为这里0~25枚举 26为z合并后的可能无法跳过。
}
}
bool check(int l,int r)
{
for(int i=20;i>=0;i--)
{
if(nxt[l][i]==r+1)return true;
if(nxt[l][i]<r+1)l=nxt[l][i];
}
return false;
}
int main()
{
int l,r,m;
scanf("%s",a+1);
n=strlen(a+1);
for(int i=1;i<=n;i++) a[i]-='a';
pre();
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
if(check(l,r))puts("Yes");
else puts("No");
}
}
