我果然还是太菜了，就写了两道题....真是水死了....
A The Miracle and the Sleeper
简化题意：给定(l，r)，求(a)%(b)的最大值，其中(r>=a>=b>=l).
这里规定了是大的数模小的数，考虑选定一个(b)，显然(a)必须比他大，则b%b=0，（b+1）%b=1，（b+2）%b=2...（2b-1）%b=b-1，之后就又从0开始到b-1，显然若(2b-1<=r)的话我们就能取到在模b的意义下的最大值，还有的是我们想让这个b足够大，才能满足我们的期望。也就是说对于一个数x在其2x-1处恰取到最大值。那么最好的情况就是2bx-1=r,这样的话，恰好在r处取到模bx意义下的最大值。这样比bx大的，取不到bx-1，比bx小的，更取不到bx-1。但这只是奇数的情况，若r为偶数的话怎么办，有两种想法，让r-1恰取到最大值，和r+1恰取到最大值，经过计算发现这样的话得到的值都是一样的都为r/2。但让r+1取到最大值，要求的值为r/2+1比r-1取到最大值要求的值为r/2，相比下前者更容易满足l的限制。还有一个问题那如果我们要求的恰好取到最大值的x（或b）小于l怎么办呢，你想一下，你的x是从x开始到r恰好取到最大值，但x小于l，那说明从l开始到r都取不到l-1，此时一定数从l开始更优！完毕！
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
int main()
{
//freopen("1.in","r",stdin);
int get(T);
while(T--)
{
int get(l),get(r);
if(r%2==0)
{
if(r/2+1>=l) cout<<r/2-1<<endl;
else cout<<r-l<<endl;
}
else
{
int s=r+1;
if(s/2>=l) cout<<s/2-1<<endl;
else cout<<r-l<<endl;
}
}
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.
B. Scenes From a Memory
B题啊，气人我把57当成质数了....气死！57=19*3，估计我能记一辈子了...
这个题我们其实可以将所有的答案给预先找出来，这样直接查找就行了，答案最多是两位数。
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=100;
int vis[N],n;
char c[N];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
int main()
{
//freopen("1.in","r",stdin);
int get(T);
while(T--)
{
get(n);scanf("%s",c+1);
int id=0;
rep(i,1,n)
{
if(c[i]=='1'||c[i]=='4'||c[i]=='6'||c[i]=='8'||c[i]=='9')
{
id=c[i]-'0';
break;
}
}
if(id) {put(1);put(id);continue;}
memset(vis,0,sizeof(vis));
rep(i,1,n)
{
if(c[i]=='2'&&i!=1)
{
id=(c[i-1]-'0')*10+2;
break;
}
else if(c[i]=='5'&&i!=1)
{
id=(c[i-1]-'0')*10+5;
break;
}
else if(c[i]=='3'&&vis[3])
{
id=33;break;
}
else if(c[i]=='7'&&vis[7])
{
id=77;break;
}
else if(c[i]=='7'&&vis[2])
{
id=27;break;
}
else if(c[i]=='7'&&vis[5])
{
id=57;break;
}
vis[c[i]-'0']=1;
}
put(2);put(id);
}
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.
C. Rings
看完题解的我眼泪流下来...
简化题意：给定一个长度为n的01串表示一个二进制数，你需要截取两个不同的且长度都必须大于等于(frac{n}{2})（向下取整）的区间，使得这两个区间转换成两个十进制数后互为倍数关系，这不妥妥的构造题吗,我怎么死在上面了....
由于2进制数肯定和2有关系，我们先尝试用2的倍数看能不能搞事情，容易发现，我们若截取了l，r，考虑l-1，r为若l-1为0，那妥妥的一倍关系就行，考虑l，r+1，若r+1为0，那不就是两倍的关系吗？找到什么规律了吗？也就是说只要这个01串中有0的话，我们就可以顺着这个0在前面（或后面）截取长度为n/2的字串就可以构造答案了，为什么有0就行，因为往前往后都可以构造，这样的话一定能构造出答案。那接下来考虑全是1的情况，那这不是更是白给吗？我们随便截取两端全是1的就是1倍的关系。完毕！
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=2e4+10;
int n,T;
char c[N];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
int main()
{
//freopen("1.in","r",stdin);
get(T);
while(T--)
{
get(n);
scanf("%s",c+1);
bool flag=false;
rep(i,1,n)
{
if(c[i]=='0')
{
flag=true;
if(i-n/2>=1)
printf("%d %d %d %d
",i-n/2,i,i-n/2,i-1);
else if(i+n/2<=n)
printf("%d %d %d %d
",i,i+n/2,i+1,i+n/2);
break;
}
}
if(flag) continue;
printf("%d %d %d %d
",1,n/2,2,n/2+1);
}
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.
D1. Two Hundred Twenty One (easy version)
这个题的题意是真的难理解啊....
简化题意：给你一个序列，其中序列中每个数的值要么1要么-1，且每个位置上都有一个符号满足奇数位为+，偶数位为-，给你q个询问，每个询问给你一个区间，求区间里至少去掉多少个数，才能使得这个区间和为0，注意去掉一个数后，后面所有的数都向前平移。其实这句话的意思就是所有数的符号变为前面数的符号。考虑去掉一个数，对前面数肯定没影响，对后面的数的影响就是所有数的符号取反，其实就是后面数的和取反。考虑对于一个区间而言，若区间和为奇数，那么肯定存在一个中间的数，其前面的和等于后面的和，那么我们将这个数去掉，后面的数取反，和为0为最优的情况，那和为偶数的呢？一次显然不够，那我么可以随便去掉一个数，使其和变为奇数，再按上述操作就行。完毕！
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=3e5+10;
int T,a[N],n,q;
char c[N];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
int main()
{
//freopen("1.in","r",stdin);
get(T);
while(T--)
{
get(n);get(q);
scanf("%s",c+1);
rep(i,1,n) a[i]=a[i-1]+(((c[i]=='+'&&i%2==1)||(c[i]=='-'&&i%2==0))?1:-1);
rep(i,1,q)
{
int get(x),get(y);
int s=a[y]-a[x-1];
if(s==0) put(0);
else if((s%2+2)%2==1) put(1);
else put(2);
}
}
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.
D2. Two Hundred Twenty One (hard version)
这个在上个的基础上要求输出方案。
考虑奇数的话，我们想要找到那个特殊的位置，直接二分就行。
偶数的话，我们可以将区间左端点去掉，再二分。