P76
竞赛时间： ????年??月??日??:??-??:??
| 题目名称 | 他 | 她 | 它 |
| 名称 | he | she | it |
| 输入 | he.in | she.in | it.in |
| 输出 | he.out | she.out | it.out |
| 每个测试点时限 | 1 秒 | 1 秒 | 1 秒 |
| 内存限制 | 512MB | 512MB | 512MB |
| 测试点数目 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 |
| 是否有部分分 | 无 | 无 | 无 |
| 题目类型 | 传统 | 传统 | 传统 |
他
【问题描述】
一张长度为N的纸带， 我们可以从左至右编号为0 − N（ 纸带最左端标号为
0）。 现在有M次操作， 每次将纸带沿着某个位置进行折叠， 问所有操作之后纸带
的长度是多少。
【输入格式】
第一行两个数字N, M如题意所述。
接下来一行M个整数代表每次折叠的位置。
【输出格式】
一行一个整数代表答案。
【样例输入】
5 2
3 5
【样例输出】
2
【样例解释】
树上有只鸟。
【数据规模与约定】
对于60%的数据， N, M ≤ 3000。
对于100%的数据， N ≤ 10^18, M ≤ 3000。
暴力60
/*暴力60 似乎离散化一下好的多...考试的时候没时间了23333*/
#include<cstdio>
#define maxn 3010
using namespace std;
int n,m,a[maxn],x,P[maxn],c[maxn][maxn],f[maxn][maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int max(int x,int y){
return x>y?x:y;
}
int main()
{
freopen("he.in","r",stdin);
freopen("he.out","w",stdout);
n=init();m=init();
for(int i=;i<=n;i++)
c[i][++c[i][]]=i,P[i]=i;
int p,s1,s2,len=n;
while(m--){
x=init();p=P[x];
s1=p;s2=len-p;
if(s1<s2){
for(int i=p+,k=p-;k>=;i++,k--)
for(int j=;j<=c[k][];j++)
c[i][++c[i][]]=c[k][j];
for(int i=p,k=;i<=len;i++,k++){
c[k][]=;
for(int j=;j<=c[i][];j++){
c[k][++c[k][]]=c[i][j];
P[c[i][j]]=k;
}
}
}
else{
for(int i=p+,k=p-;i<=len;i++,k--)
for(int j=;j<=c[i][];j++){
c[k][++c[k][]]=c[i][j];
P[c[i][j]]=k;
}
}
len=max(s1,s2);
}
printf("%d\n",len);
return ;
}
离线就100....
/*离散化.... 考试的时候脑抽拿n直接做的*/
#include<cstdio>
#define ll long long
#define maxn 3010
#ifdef unix
#define LL "%lld\n"
#else
#define LL "%I64d\n"
#endif
using namespace std;
ll n,m,a[maxn],c[maxn];
ll init(){
ll x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
ll max(ll x,ll y){
return x>y?x:y;
}
ll min(ll x,ll y){
return x<y?x:y;
}
int main()
{
freopen("he.in","r",stdin);
freopen("he.out","w",stdout);
n=init();m=init();
for(int i=;i<=m;i++)
c[i]=init();
for(int p=;p<=m;p++){
ll P=c[p],mi=P*-n;//这个才是右端点 不是P*2-c[m]233s
ll s1=P,s2=n-P;n=max(s1,s2);
for(int i=;i<=m;i++)
if(c[i]>P)c[i]=*P-c[i];
if(mi<)for(int i=;i<=m;i++)
c[i]-=mi;
}
printf(LL,n);
return ;
}
她
【问题描述】
给你M, S, L, R， 求满足L ≤ (S × x) mod M ≤ R最小的正整数x。
【输入格式】
第一行一个数T代表数据组数。
接下来T行每行四个数代表该组数据的M, S, L, R。
【输出格式】
对于每组数据， 输出一行代表答案。 如果不存在解， 输出“ −1”。
【样例输入】
1
5 4 2 3
【 样例输出】
2
【 样例解释】
叫南小鸟。
【数据规模与约定】
对于30%的数据， 保证有解且答案不超过10^6。
对于另外20%的数据， L = R。
对于100%的数据， 1 ≤ T ≤ 100,0 ≤ M, S, L,R ≤ 10^9。
暴力50
/*这题无了语了 本来50来 想了想 嗯都用gcd搞吧 可能快点 然后就20了*/
#include<iostream>
#include<cstdio>
#define maxn 1000000
#define ll long long
#define inf 1e9+10
using namespace std;
ll T,M,S,L,R,x,y,gcd,ans;
ll init(){
ll x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
ll min(ll x,ll y){
return x<y?x:y;
}
void Cl(){
ans=inf;x=;y=;gcd=;
}
void Gcd(ll a,ll b){
if(b==){x=;y=;gcd=a;}
else{
Gcd(b,a%b);
ll tmp=x;x=y;y=tmp-a/b*y;
}
}
void Solve1(){
if(S%M==){
ans=-;return;
}
Gcd(S,M);int r=,falg=;
for(int c=L;c<=R;c++){
if(c%gcd)continue;
ll tmp=x*c/gcd;r=M/gcd;
tmp=(tmp%r+r)%r;falg=;
if(tmp==)tmp+=r;
ans=min(ans,tmp);
}
if(falg==)ans=-;
}
void Solve2(){
if(S%M==){
ans=-;return;
}
int falg=;
for(x=;x<=;x++){
ll r=(S*x)%M;
if(r>=L&&r<=R){
falg=;break;
}
}
if(falg)ans=x;
else ans=-;
}
int main()
{
freopen("she.in","r",stdin);
freopen("she.out","w",stdout);
T=init();
while(T--){
M=init();S=init();
L=init();R=init();
Cl();
if(R==L)Solve1();
else Solve2();
cout<<ans<<endl;
}
return ;
}
正解嘛 你猜
它
【问题描述】
N个人坐成一圈， 其中第K个人拿着一个球。 每次每个人会以一定的概率向
左边的人和右边的人传球。 当所有人都拿到过球之后， 最后一个拿到球的人即为
胜者。 求第N个人获胜的概率。（ 所有人按照编号逆时针坐成一圈）
【输入格式】
第一行一个数T代表数据组数。
对于每组数据， 第一行两个整数N, K如题意所述。
接下来每行一个实数p代表该人将球传给右边的人的概率。
【输出格式】
对于每组数据， 一行一个实数代表答案， 保留9位小数。
【样例输入】
1
5 1
0.10
0.20
0.30
0.40
0.50
【 样例输出】
0.007692308
【 样例解释】
然后鸟是我的。
【数据规模与约定】
对于20%的数据， N ≤ 3。
对于70%的数据， T, N ≤ 100。
对于100%的数据， T ≤ 10000,1 ≤ N ≤ 100。
Orz...
/*还有待研究2333*/
#include<cstdio>
#define maxn 110
#define ld long double
using namespace std;
int T,n,k,a[maxn],b[maxn];
ld p[maxn],q[maxn],P,Q,ans;
void Cal(int m){
/*int l=a[m],r=b[m];
q[l]=(q[m]*q[l])/(1-q[m]*p[l]);
p[l]=1-q[l];
p[r]=(p[m]*p[r])/(1-p[m]*q[r]);
q[r]=1-p[r];
b[l]=r;a[r]=l;*/
int l=a[m],r=b[m];
long double pa=p[l],pb=p[m],pc=p[r];
p[l]=pa*pb/(-pa*(-pb));q[l]=-p[l];
q[r]=(-pc)*(-pb)/(-pb*(-pc));p[r]=-q[r];
b[l]=r;a[r]=l;
}
int main()
{
freopen("it.in","r",stdin);
freopen("it.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){
scanf("%llf",&p[i]);
q[i]=-p[i];
a[i]=i-;b[i]=i+;
}
a[]=n;b[n]=;
if(n==)ans=;
else if(n==)k==?-q[]:-p[];
else if(k==){
for(int i=;i<n-;i++)Cal(i);ans=-q[];
}
else if(k==n-){
for(int i=;i<n-;i++)Cal(i);ans=-p[n-];
}
else {
for(int i=;i<k;i++)Cal(i);
for(int i=k+;i<n;i++)Cal(i);
ans=q[k]*p[]+q[n-]*p[k];
}
printf("%.9f\n",double(ans));
}
return ;
}