满分：300分
直接全部爆零，真的是很坑啊！
10.30的题目+数据：链接：http://pan.baidu.com/s/1jHXLace 密码：i784
T1:
题目中的难点就是每次折叠的点可能应经被覆盖了，我的做法是递归去推出它现在在哪个位置，不仅超时，而且答案错误。
也曾想过用数组去存下它当前的位置，但是被10^18的数据吓到了。
正解：并不是所有的坐标都有用，仅仅是那m个将要用到的点有用，所以每次折叠，就只对之后的有用的k个点进行更新，这样就行了。
时间复杂度O(m^2) 不会超时的。
#include<iostream>
using namespace std;
#include<cstdio>
#define M 3004
typedef long long ll;
ll pos[M];
ll n,m;
int main()
{
freopen("he.in","r",stdin);
freopen("he.out","w",stdout);
cin>>n>>m;
for(int i=;i<=m;++i)
cin>>pos[i];
ll l=,r=n;
for(int i=;i<=m;++i)
{
ll x=pos[i];
if(*x>=(l+r))
{
r=x;
for(int j=i+;j<=m;++j)
if(pos[j]>x) pos[j]=x+x-pos[j];
}
else
{
l=x;
for(int j=i+;j<=m;++j)
if(pos[j]<x) pos[j]=x+x-pos[j];
}
}
cout<<r-l;
fclose(stdin);
fclose(stdout);
return ;
}
T2：相信大牛们一眼就看出了这道题目用BSGS算法。注明：该算法我不会。
只会50分。
/*
扩展欧几里得模板打错了。 */
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &x,ll &y,ll &gc)
{
if(!b)
{
x=;y=;
gc=a;
return;
}
exgcd(b,a%b,y,x,gc);
y-=(a/b)*x;
}
ll read()
{
ll ret=,ff=;
char s1=getchar();
while(s1<''||s1>'')
{
if(s1=='-') ff=-;
s1=getchar();
}
while(s1>=''&&s1<='')
{
ret=ret*+s1-'';
s1=getchar();
}
return ret*ff; }
int main()
{
freopen("she.in","r",stdin);
freopen("she.out","w",stdout);
ll l,r,s,m;
int T;
scanf("%d",&T);
while(T--)
{
//cin>>m>>s>>l>>r;
m=read();s=read();l=read();
r=read();
if(l>=m)
{
printf("-1\n");
continue;
}
if(l==r)
{
ll x,y,gc;
exgcd(s,m,x,y,gc);
if(l%gc)
{
cout<<-<<endl;
}
else
{
x=x*l/gc;
ll m1=m/gc;
x=(x%m1+m1)%m1;
if(x==) x+=m1;
cout<<x<<endl;
}
continue;
}
bool flag=false;
for(int x=;x<=;++x)
{
ll res=(s%m*x%m)%m;
if(res>=l&&res<=r)
{
printf("%d\n",x);
flag=true;
break;
}
}
if(flag) continue;
printf("-1\n");
}
fclose(stdin);
fclose(stdout);
return ;
}
标程：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm> using namespace std; const int maxn=; int L,R,s,m; struct rec
{
int v,p;
bool operator<(const rec &a)const
{
return v<a.v;
}
}z[maxn]; void solve(int l,int r,int &res,int delta,int p)
{
if (l>r) return;
int left=l-,right=r;
while (left+!=right)
{
int mid=(left+right)>>;
if ((z[mid].v+delta)%m>=L) right=mid;
else left=mid;
}
int v=z[right].v+delta;
v%=m;
if (v>=L && v<=R)
{
for (int a=l;a<=r;a++)
if ((z[a].v+delta)%m>=L && (z[a].v+delta)%m<=R)
{
if (res) res=min(res,z[a].p+p-);
else res=z[a].p+p-;
}
}
} int main()
{
freopen("she.in","r",stdin);
freopen("she.out","w",stdout); int test;
scanf("%d",&test);
for (int p=;p<=test;p++)
{
scanf("%d%d%d%d",&m,&s,&L,&R);
if (R>=m) R=m-;
s%=m;
int size=(int)sqrt(m);
int res=;
for (int a=;a<=size && !res;a++)
{
z[a].v=(z[a-].v+s)%m;
if (z[a].v>=L && z[a].v<=R) res=a;
z[a].p=a;
}
sort(z+,z+size+);
for (int a=size+;a<=m && !res;a+=size)
{
int delta=(long long)size*s%m*((a-)/size)%m;
int l=,r=size;
while (l+!=r)
{
int mid=(l+r)>>;
if (z[mid].v+delta>=m) r=mid;
else l=mid;
}
if (z[r].v+delta<m) r++;
solve(,r-,res,delta,a);
solve(r,size,res,delta,a);
}
if (res) printf("%d\n",res);
else printf("-1\n");
} return ;
}
T3：听说很难，我不会，只有标程
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm> using namespace std; const int maxn=; int n,k,pre[maxn],next[maxn]; long double p[maxn],q[maxn]; void del(int b)
{
int a=pre[b],c=next[b];
long double pa=p[a],pb=p[b],pc=p[c];
p[a]=pa*pb/(-pa*(-pb));q[a]=-p[a];
q[c]=(-pc)*(-pb)/(-pb*(-pc));p[c]=-q[c];
next[a]=c;pre[c]=a;
} long double solve()
{
if (n<=) return ;
if (n<=) return k== ? p[] : q[];
for (int a=;a<=n;a++)
pre[a]=a-,next[a]=a+;
pre[]=n;next[n]=;
if (k==)
{
for (int a=;a<n-;a++)
del(a);
return p[];
}
if (k==n-)
{
for (int a=;a<n-;a++)
del(a);
return q[n-];
}
for (int a=;a<k;a++)
del(a);
for (int a=k+;a<n-;a++)
del(a);
del(k);
return q[k]*p[]+p[k]*q[n-];
} int main()
{
freopen("it.in","r",stdin);
freopen("it.out","w",stdout); int test;
scanf("%d",&test);
for (int px=;px<=test;px++)
{
scanf("%d%d",&n,&k);
for (int a=;a<=n;a++)
{
double v;
scanf("%lf",&v);
p[a]=v;
q[a]=-p[a];
}
printf("%.9lf\n",(double)solve());
} return ;
}