Div1 534
我可能还太菜了. jpg
果然我只是 Div 2 选手
A
(这题是 Div1 吗...
直接构造: 竖着放的在第一行和第二行, 然后横着放的时候直接放在第三行就行.
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <cstdlib>
- #include <queue>
- #include <iostream>
- #include <bitset>
- using namespace std;
- #define N 1005
- char s[N];int n;
- int main()
- {
- scanf("%s",s+1);n=strlen(s+1);
- for(int i=1,now1=0,now2=0;i<=n;i++)
- {
- if(s[i]=='1')
- {
- if(now1)printf("1 3\n");
- else printf("1 1\n");
- now1^=1;
- }else
- {
- printf("%d %d\n",3,now2+1);
- now2++;now2%=4;
- }
- }
- }
- B
看到 $60$ 就知道是二分或者倍增...
然后发现, 正解是二分 + 倍增...
首先, 我们知道, 如果 $a$ 在 $2^k\sim 2^{k+1}$ 之间, 那么, 在询问 $2^{k-1},2^k$ 的时候, 可以知道一定是后者大于前者...
所以在询问 $2^{k-i-1},s^{k-i}$ 的时候同样...
而在询问 $2^{k}, 2^{k+1}$ 的时候, 一定是前者大于等于后者.
所以就可以二分出来一个位置 $x$, 满足 $x\mod a<2^{k+1}\mod a$
然后就行了. jpg
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <cstdlib>
- #include <queue>
- #include <iostream>
- #include <bitset>
- using namespace std;
- char s[15];
- int cnt=0;
- bool ask(int x,int y)
- {
- cnt++;
- printf("? %d %d\n",x,y);
- fflush(stdout);
- scanf("%s",s);
- if(s[0]=='x')return 1;
- else return 0;
- }
- int main()
- {
- while(1)
- {
- scanf("%s",s);cnt=0;
- if(s[0]=='e'||s[0]=='m')return 0;
- int i;
- for(i=1;i<=1000000000;i<<=1)if(ask(i,i<<1))break;
- int l=i,r=i<<1,ans=-1;
- while(l<=r)
- {
- int m=(l+r)>>1;
- if(ask(m,i<<1))l=m+1;
- else r=m-1,ans=m;
- }
- if(ans!=-1)printf("! %d\n",ans);
- else
- {
- if(ask(i<<1,i))printf("! %d\n",i);
- else printf("! %d\n",i<<1);
- }
- fflush(stdout);
- }
- }
- C
暂时还不会...
D
先求一个 $\gcd$, 然后排个序, 显然最多只会打 $\gcd$ 的质因子个数次
然后显然对于所以的质因子, 做一个状压 DP 即可...
来源: http://www.bubuko.com/infodetail-2945238.html