我的csdn链接
四题下班,每次D2都做不出或者没啥时间了…
大胆假设,猜到结论就可以冲了(bushi
A. The Miracle and the Sleeper
题目链接
题意: 已知两个整数$l$和$r$, $l≤r$。求所有$r≥a≥b≥l$的整数对$(a,b)$中$a$ $mod$ $b$的最大可能值。
分析: 在给定的$l,r$中,选择$r≥a≥b≥l$,的$a,b$使得$a mod b$最大。可以想到如果有数$x$,使得$r$$\div$$x=1......x-1$,这样的$x$最大是多少?$r=2x-1$,$x=(r+1)/2$,如果$l \leq (r+1)/2$,那么答案就是$(r+1)/2-1$。
否则,即$l \geq (r+1)/2$时,只能这样构造,$r \div l=1.....r-l$,答案也就是$r-l$。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
int t;scanf("%d",&t);
while(t--){
int l,r;scanf("%d %d",&l,&r);
if((r+1)/2>=l)printf("%d\n",(r+1)/2-1);
else printf("%d\n",r%l);
}
return 0;
}
B. Scenes From a Memory
题目链接
题意: 给定一个正整数n,它在十进制表示法中不包含零。问:这个数最多可以去掉多少位数字,这样这个数就不是质数了。
分析: 仔细分析,从一大串数字删掉最多的数字后,剩下的数是一个合数。看了样例之后大胆猜测剩下的位数不是1就是2,然后莽了一发对了(不要学我)。
其实仔细分析,因为答案保证一定有解,假设剩下的数是三位。能找到一个三位数,使得这个三位数是一个合数,但是其任意两个数组成的两位数不是合数吗。感觉证明不是很科学。起床之后再想想......起床了
我们来证明一下,如果一个数是三位数,你总是可以从其中至少删除一个数来得到一个数不是质数。
法一:可以通过对所有三位数的数字爆搜来得到解,我没有写了,大家可以试试。
法二:如果一个数中包含$1,4,6,8,9$,那么其中任意一个数字就是答案,这几个数都是非素数。
如果一个三位数中没有这些数字呢?也就是只包含$2,3,5,7$。
- 如果这个数中,存在$2$或者$5$不在第一位,那么可以删掉一个数变成合数。比如$752$,$723$中选择$75$和$72$。
- 如果是存在任意两个相同的数,比如$22,33,55,77$,这些数都是合数。
- 同时包含$5,7$的数,是肯定能够构成$57$或$75$,能被$3$整除,是合数。
- 剩下的情况就是,$273,237$,删除$3$即可构成$27$,能被$3$整除,也是合数
所以上述就证明了,留下来的数字肯定不超过两位,然后直接暴力模拟就行了。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=55;
char s[N];
bool check(int x){
if(x<=3)return x>1;
if(x%2==0||x%3==0)return 0;
for(int i=5;i<=sqrt(x);i+=6){
if(x%i==0||x%(i+2)==0)return 0;
}
return 1;
}
int main()
{
int t;scanf("%d",&t);
while(t--){
int n,flag=0;scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;s[i];i++){
int p=s[i]-'0';
if(!check(p)){
printf("%d\n%d\n",1,p);
flag=1;
break;
}
}
if(flag)continue;
for(int i=1;s[i];i++){
for(int j=i+1;s[j];j++){
int p=(s[i]-'0')*10+s[j]-'0';
if(!check(p)){
printf("%d\n%d\n",2,p);
flag=1;
break;
}
}
if(flag)break;
}
}
return 0;
}
C. Rings
题目链接
题意: 给定一个01串,从中选出两个长度大于等于$\lfloor \frac{n}{2} \rfloor$的区间$t$和$w$,使得两个区间所构成的十进制数满足$f(t)=f(w)⋅k$。($f(x)$就是$x$的十进制数,$k$为非负整数)
分析: 很巧妙的题目,这个题目就分为两种情况讨论。
- 全为$1$,这种情况只需要输出长度大于等于$n/2$的两个区间,且这两个区间长度为倍数关系即可。我直接输出了$1,n/2*2;1,n/2$
- 不全为$1$,在$0001000$中,可以选择$0001000,001000$,在$100100$中,选择$00100$,$0100$。可以看出些什么?
从左往右在前面一半的数中,找到第一个$0$,可以看出$0x$($x$是0右边的任意$01$串)和$x$是相等的。所以直接从当前0的位置,直接输出答案到结尾,另一个部分就是当前0后面的位置到结尾。
在后面一半中,从右往左找一遍。同理,$1111000$中选择$1111000$和$111100$是可行解。$x0$(x是0左边的任意01串)等于$x \times 2$,所以选择的两个部分分别是,从首位到当前0的位置,从首位到当前0前面的一个位置。
非常巧妙的题目。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=2e4+5;
char s[N];
int main()
{
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
scanf("%s",s+1);
int flag=0;
for(int i=1;i<=n/2;i++){
if(s[i]=='0'){
printf("%d %d %d %d\n",i,n,i+1,n);
flag=1;
break;
}
}
if(!flag){
for(int i=n;i>n/2;i--){
if(s[i]=='0'){
printf("%d %d %d %d\n",1,i,1,i-1);
flag=1;
break;
}
}
}
if(!flag)printf("%d %d %d %d\n",1,n/2*2,1,n/2);
}
return 0;
}
D1. Two Hundred Twenty One (easy version)
题目链接
题意: 一台机器的主要部件是沿着一条直线排列的$n$根杆,编号从$1$到$n$。每个这些杆必须携带一个$1$或$-1$的电荷(否则机器将不工作)。
这台机器工作的另一个条件是,所有杆上的电荷的符号变量之和必须为零。也就是要满足$a_{1}−a_{2}+a_{3}−a_{4}+…=0$ , or $\sum_{i=1}^{n}{(-1)^{i-1}}\cdot a_{i}=0$。在第$i$个问题中,如果机器只由数为$l_{i}$到$r_{i}$的杆组成,那么最小多少杆可以从机器中移除,以使其余杆上的符号可变的电荷之和为零?也就是通过上面的式子算完之后为0。
分析:
做的时候又是看样例盲猜一手结论,答案就是$0,1,2$,然后简单证明了一下。
结论: 奇数肯定只能删$1$个,偶数判断一下是不是$0$,不是$0$就是$2$。判断是不是$0$需要先与处理一下前缀和。证明早上再补叭,困了( ̄o ̄) . z Z 醒了
证明: :感觉官方的证明很可,我这里翻译加自己的话解释一下。引入一个新的数组$b$,如果移除第$i$个元素,则$b_{i}$等于整个数组的按照题意的带符号和。
对于一个串$a$
- 如果$a_{i}=a_{i+1}$,那么$a_{i}$被移除时,和$a_{i+1}$被移除时的效果是一样的$|b_{i}-b_{i+1}|=0$。
- 如果$a_{i} \not= a_{i+1}$,用$f(l,r)$表示区间$l$到$r$的符号变量和。容易得到,$b_{i}=f(1,i−1)±a_{i+1}∓f(i+2,n)$,$b_{i+1}=f(1,i)∓f(i+2,n)$。所以$b_{i}-b_{i+1}=∓a_{i}±a_{i+1}$,因为$a_{i} \not= a_{i+1}$,所以$|b_{i}-b_{i+1}|=2$.
如果$n$是奇数,那么存在$k$使$b_{k}=0$。
证明:
- 如果$b_{1}=0$或$b_{n}=0$,则得证。
- 如果$b_{1}<0,b_{n}>0$,因为数组中相邻的值$b$相差要么为$2$,要么为$0$,所有的元素都是偶数,而且相邻b的差值不可能存在连续的2,只可能是2和-2交替,或者是0。要使得$b_{1}<0,b_{n}>0$,那么从$1-n$的之间的$b$值肯定存在一个是$0$。
- $b_{1}>0,b_{n}<0$同理
- 如果$n>1$,则不可能有$b_{1}>0$和$b_{n}>0$的情况,也不可能有$b_{1}<0$和$b_{n}<0$的情况。
$n$为偶数的时候,同理,可以删除一个数之后转换为奇数的情况。如果变量和已经为0了,答案就是0
设整段的符号变量和为$sum$,则$b_{1}= - sum±1$,$b_{n}=sum±1$。因为$b_{1}$和$b_{n}$是偶数,所以它们中至少有一个是零,或者它们的符号不同。
所以,如果变量和已经为零,输出为零;否则,如果段是奇数长度,输出1;偶数长度,输出2。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=300005;
char s[N];
int sum[N];
int main()
{
int t;scanf("%d",&t);
while(t--){
int n,q;scanf("%d %d",&n,&q);
scanf("%s",s+1);
if(s[1]=='+')sum[1]=1;
else sum[1]=-1;
for(int i=2;i<=n;i++){
if(s[i]=='+')sum[i]=sum[i-2]+1;
else sum[i]=sum[i-2]-1;
}
while(q--){
int l,r;scanf("%d %d",&l,&r);
if((r-l+1)%2)printf("1\n");
else{
int ju=sum[r-1]-sum[l-2]-(sum[r]-sum[l-1]);
//cout<<ju<<endl;
if(!ju)printf("0\n");
else printf("2\n");
}
}
}
return 0;
}
D2. Two Hundred Twenty One (hard version)
题目链接
题意: 和上题意思一致,加了一个要求,需要输出你删除的杆是哪一个。
分析: 上题已经得出来了一些结论。
- 如何在奇数段中找到要删除哪一个元素。如果暴力枚举每一个元素,肯定会TLE。考虑一下b数组中的函数形式,b数组画出来的函数图要么是经过x轴的一次函数,要么为三次函数,(只是类似这种形式,因为b数组两两差值可能为0)这就给了我们二分的机会。假设一开始$l=1,r=n$,因为$b_{1}$和$b_{n}$符号相同或者至少其中一个为$0$。
- 每一次找到$mid= \lfloor \frac{l+r}{2} \rfloor$,如果$b_{mid}=0$或者$b_{l}=0$或者$b_{r}=0$,我们就都找到了一个可行解。否则,如果$b_{l}$和$b_{mid}$符号一致,那么需要在$mid$的右半边找,更新$l$为$mid$。否则,要在$mid$的左半边找,$r=mid$。
这样算最终一定会得到一个答案,因为我们知道一定存在一个$i$使得$b_{i}=0$。这可以用$|bi−bi+1|≤2$,而且所有$b_{i}$都是偶数来证明,前面一题其实也说过了。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=300005;
char s[N];
int sum[N];
int to_sum(int l,int r){
if(l>r)return 0;
return (l%2==1?sum[r]-sum[l-1]:sum[l-1]-sum[r]);
}
int get_b(int l,int r,int m){//这一部分就是在求我们定义的b
int ans=to_sum(l,m-1);
if((m-l+1)%2)ans+=to_sum(m+1,r);//后面半部分的计算,需要根据删除的m位置的正负来判断
else ans-=to_sum(m+1,r);
return ans;
}
int get_sign(int x){
return x>0?1:-1;
}
int find_ans(int l,int r){
if(l==r)return l;
int la=l,ra=r;
while(la<ra){
int mid=la+ra>>1;
int lb=get_b(l,r,la);//l到r删去la
int mb=get_b(l,r,mid);//l到r删去mid
int rb=get_b(l,r,ra);//l到r删去ra
if(lb==0)return la;
if(mb==0)return mid;
if(rb==0)return ra;
if(get_sign(lb)==get_sign(mb))la=mid;
else ra=mid;
}
return -1;
}
int main()
{
int t;scanf("%d",&t);
while(t--){
int n,q;scanf("%d %d",&n,&q);
scanf("%s",s+1);
for(int i=1;i<=n;i++){
if(i%2)sum[i]=sum[i-1]+(s[i]=='+'?1:-1);
else sum[i]=sum[i-1]-(s[i]=='+'?1:-1);
}
while(q--){
int l,r;scanf("%d %d",&l,&r);
if(!to_sum(l,r))printf("0\n");
else{
bool is_even=false;
if((r-l+1)%2==0)is_even=true,l++;
int pos=find_ans(l,r);
if(is_even)printf("2\n%d %d\n",l-1,pos);
else printf("1\n%d\n",pos);
}
}
}
return 0;
}