[NOIP模擬賽]
[測評環(huán)境：windows]
[hzq84621]
除草
文件名： weed
題目類型： 傳統(tǒng)題
時間限制： 1秒
內(nèi)存限制： 128MB
編譯優(yōu)化： 無
題目描述
小A有一塊三角形的草坪。
小A還有一個圓形的除草機，把它放在草坪里就可以對一整個圓形區(qū)域就行除草。
但是由于草坪邊界有柵欄，除草機并不能做到對整個草坪做到除草，因為除草機不能越過柵欄。
如果無法理解可以看一下目錄下的png文件。
為了防止精度誤差，你需要輸出的是能夠除草的面積/總草坪面積
輸入格式
四個正整數(shù)，前三個正整數(shù)描述三角形三邊長度，最后一個正整數(shù)描述除草機半徑。
輸出格式
共一個實數(shù)表示能夠除草的區(qū)域的面積，你的答案和實際答案誤差不超過0.000001即認(rèn)為正確。
樣例輸入
3 4 5 1
樣例輸出
0.5235987755982
數(shù)據(jù)規(guī)模與約定
對于50%的數(shù)據(jù)滿足給出的是一個直角三角形
對于100%的數(shù)據(jù)， 輸入的所有數(shù)字不超過10000
出題人的關(guān)懷
海倫公式：
定義p=(a+b+c)/2
三角形面積S=\sqrt{p(p-a)(p-b)(p-c)}
顯然怎么樣做都行，無非是麻不麻煩和精度怎么樣。
這里給一種比較簡單的做法。
不難發(fā)現(xiàn)當(dāng)r變化時不能被夠到的部分其實是形狀相同大小不同的，也就是相似的。
那么我們不妨算出內(nèi)接圓情況的答案，然后按照r和內(nèi)接圓半徑的比例縮放即可。
/*#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;//內(nèi)切圓半徑
// 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;//考場上居然沒想到用圓半徑相似。。被初二小學(xué)妹吊打。。。
// cout<<ss<<endl;
// cout<<yuan<<endl;
printf("%.15lf",1.0*(s-ss+yuan)/s);
}
跳棋
文件名： chess
題目類型： 傳統(tǒng)題
時間限制： 1秒
內(nèi)存限制： 128MB
編譯優(yōu)化： 無
題目描述
小A是跳棋大師。
跳棋的規(guī)則是，一顆棋子可以移動一個單位，或者移動越過一個另一個棋子運動一個單位。
小A在一條數(shù)軸上放了n顆棋子，第i顆棋子位于a_{i}的位置，然后給了每個棋子一個編號。
現(xiàn)在小A想要知道，所有跳棋到達0的可能順序有多少種。
出于某些模因污染，小A只會向左移動跳棋。
輸入格式
第一行一個整數(shù)n
接下來一行n個整數(shù)描述a_{i}
保證a_{i}
輸出格式
一個整數(shù)，表示可能的方案數(shù),mod 1000000007后輸出
樣例輸入
3
1 2 3
樣例輸出
4
樣例解釋
3不能同時越過1和2，所以可行的順序有123,132,231,213
數(shù)據(jù)規(guī)模與約定
對于30%的數(shù)據(jù)，滿足n≤8
對于60%的數(shù)據(jù)，滿足a_{i}>=a_{i+1}-2
另存在10%數(shù)據(jù)滿足a_{i}=i
對于100%的數(shù)據(jù)，滿足n≤1000000,0
考慮一個比較簡單的情況：
1、3、5、7、9...
這種時候答案顯然是n!因為我們可以讓任意一個棋子在其他棋子不移動的情況下成為下一個到達的棋子。
也不難證明這是最“劣”的能夠有n!種方案的情況。
棋子與棋子除了編號并沒有不同，換而言之一個棋子離開之后后面的棋子如果能夠到達他的位置就可以頂替他。
首先把所有棋子都盡可能向左靠，因為越向左靠對后面的棋子來說有更多的調(diào)整空間。
比如1 5 6 7，往左靠就可以得到1 3 5 7的情況。
當(dāng)某個位置不得不出現(xiàn)相鄰兩顆棋子距離為1的情況時，比如1、3、4，此時能夠作為下一個到達的棋子就只有前面三顆，因為后面的棋子不能同時越過相鄰的兩顆。
然后考慮一顆棋子離開了會怎樣，無論是哪顆棋子離開了，第三顆都可以到達他的位置，無論是誰離開，最后都可以到達1、3這個“較優(yōu)”的狀態(tài)。
所以這樣模擬一遍就好了。注意最后的邊界狀況。
自己粗糙的理解
一顆棋子移動了并不一定要直接移去終點！?。?所以把所有棋子向左移之后是等價的
然后就會有相差二或者相鄰
兩個棋子相鄰則后面的棋子無法移動故下一步只能移動之前的棋子，而每一種又是等價的，直接把一個棋子送去終點其他棋子隔一排布
相差一的序列答案顯然是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--;//棋子個數(shù)減少
a[i]--;//i替代i-1
}
}
for(int i=now;i>=1;i--)ans=(ans*i)%mod;//剩下的數(shù)都不相鄰，方案數(shù)為now!
printf("%d",ans);
}
聚變
文件名： fusion
題目類型： 傳統(tǒng)題
時間限制： 1秒
內(nèi)存限制： 256MB
編譯優(yōu)化： 無
題目描述
知名科學(xué)家小A在2118年在計算機上實現(xiàn)了模擬聚變的過程。
我們將她研究的過程簡化。
核子共有26種，可以用a到z共26個字母表示。
核子聚變的過程可以用一個字符串描述。
按照順序從左到右的順序，假如有兩個相同核子相鄰，兩個核子就會相互吸引發(fā)生聚變生成一個序號+1的核子，特殊的，兩個z核子相鄰會湮滅沒有新的核子生成。
每當(dāng)兩個核子聚變時，就需要重新從左到右重復(fù)找到兩個相鄰的相同核子直到不存在為止。
比如zyzzy->zyy->zz->
小A為了做出足夠有效的實驗，每次會從一個字符串中選定一個子串操作。
她想要知道每次實驗這個子串中的核子能否最終全部湮滅。
輸入格式
第一行一個只有小寫字母的字符串。
第二行一個數(shù)n表示詢問次數(shù)
接下來n行每行兩個正整數(shù)l_{i},r_{i}表示詢問區(qū)間
輸出格式
對每次詢問輸出一行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
數(shù)據(jù)規(guī)模與約定
L表示字符串長度
對于30%的數(shù)據(jù)滿足L<=100
對于60%的數(shù)據(jù)滿足L<=3000,n<=3000
另存在20%數(shù)據(jù)滿足字符串中只存在y,z
對于100%的數(shù)據(jù),L<=500000,n<=1000000
倍增裸題。
60p送你
10p因為只有y,z所以一段區(qū)間處理之后一定只有y,yz,zy,z,空五種情況，所以可以數(shù)據(jù)結(jié)構(gòu)維護每個區(qū)間以這5種情況為開頭分別會是什么結(jié)果。
剩下30，直接倍增就行了。
難點在于狀態(tài)過多無法有效記錄，所以按照字符串位數(shù)倍增顯然不行。
那就按照結(jié)果倍增。
dp_{i,j}表示從第i個位置開始操作，最小的滿足從i到dp_{i,j}的操作結(jié)果為一個字符j的位置。
顯然可以倍增。
但是這樣還不夠，可能會出現(xiàn)很多次全都消完的情況，直接跑會退化成nL
Dp_{i,j}表示從第i個位置開始操作，第2^j次出現(xiàn)全部消完時的位置
然后就是通過倍增判斷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個獨立的區(qū)間后的位置
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");
}
}
