I. Cyclic Apple Strings
找 10 的个数即可
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int cnt=0;
for(int i=0;i+1<s.size();i++){
if(s[i]=='1'&&s[i+1]=='0')cnt++;
}
cout<<cnt<<endl;
}
|
K. Party Games
观察连续异或和，发现每次如果 %4 == 1 或 0 可以移走最左或最右的一个元素，反之则无法操作，或有两个元素能取，此时先手必败。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
void solve(){
cin>>n;
bool flag=0;
if(n<=3){
if(n==1)flag=1;
}
else{
int t=n%4;
if(t<=1)flag=1;
}
if(flag)cout<<"Fluttershy\n";
else cout<<"Pinkie Pie\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Countless Me
可以将所有元素加合起来后，分配到 n 个位置上
问题转化为如何分配，注意到要求的是按位或最小，明确如果某位按位或后为 1，这一位上的 1 就应该尽量多，同时，应该优先填满低位。
所以从高位往低位贪心，一次计算当前位数如果不填，sum 能否分配完，如果不能，就在当前位放尽可能多的 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
int a[N],b[32];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
ll sum=accumulate(a+1,a+1+n,0ll);
for(int i=31;i>=0;i--){
if(1ll*n*((1<<i)-1)>=sum)continue;
int x=min(n*1ll,sum/(1<<i));
b[i]=1;
// cout<<i<<" ";
sum-=x*(1<<i);
}
ll ans=0;
for(int i=0;i<=31;i++){
if(b[i])ans+=(1<<i);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
F. Custom-Made Clothes
二分答案，寻找矩阵中有多少个值小于等于其。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
// #define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n,k;
bool check(int mid){
int x=n,y=1,cnt=n;
while(x>0&&y<=n){
printf("? %d %d %d\n",x,y,mid);
cout<<endl;
bool f;
cin>>f;
if(f)y++,cnt+=x;
else x--,cnt--;
}
return cnt<=k;
}
void solve(){
cin>>n>>k;
int l=1,r=n*n,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
D. ICPC
观察时限，$O(n^2)$ 解决问题。
显然从某一位开始，只会有两种走法，一种不变向走到头，另一种变向一次，这两种就足够覆盖所有情况，即足够覆盖所有位置。
所以，先通过前缀和，求得不变向时，从某一位置开始，走 t 秒的最大值。
接着通过不变向的最大值来求有变向时的。
$f[s][t] = max(g[s][t],g[s-1][t-1],g[s-2][t-2],…,g[s+1][t-1],g[s+2][t-2],…)$
正着先求 $f[s][t]=max(f[s-1][t-1],g[s][t])$，再倒着求 $f[s][t]=max(f[s+1][t-1],g[s][t])$ 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=5e3+7, mod=1e9+7;
int n;
ll a[N],s[N],g[N][2*N],f[N][2*N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n+n;j++){
int l=max(1,i-j);
int r=min(n,i+j);
g[i][j]=max(s[i]-s[l-1],s[r]-s[i-1]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n+n;j++){
f[i][j]=max({f[i][j],f[i-1][j-1],g[i][j]});
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=n+n;j++){
f[i][j]=max({f[i][j],f[i+1][j-1],g[i][j]});
}
}
ll ans=0;
for(int i=1;i<=n;i++){
ll tmp=0;
for(int j=1;j<=n+n;j++){
tmp^=(j*f[i][j]);
}
ans^=(i+tmp);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
M. Merge
观察到，相差为 1 的两个数相加后，只能为奇数，那么要操作，就必须找到偶数，所以我们只对偶数位查询，记当前偶数为 x，我们查询 x+1, x-1 是否存在，查询过程递归，如果当前查询值存在返回 1，否则查询当前值拆分后的两个数是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
ll n,a[N];
map<ll,int>vis,tmp;
bool dfs(ll x){
if(vis[x]>0){
vis[x]--;
tmp[x]++;
return 1;
}
if((x%2)==0||(x==1))return 0;
return dfs(x/2)&&dfs(x/2+1);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
vis[a[i]]++;
}
sort(a+1,a+1+n,greater<ll>());
for(int i=1;i<=n;i++){
int t=a[i];
if(vis[t]<=0)continue;
vis[t]--;
tmp.clear();
if(dfs(t+1)){
vis[t+t+1]++;
continue;
}
for(auto [x,y]:tmp)vis[x]+=y;
tmp.clear();
if(dfs(t-1)){
vis[t+t-1]++;
continue;
}
for(auto [x,y]:tmp)vis[x]+=y;
tmp.clear();
vis[t]++;
}
vector<ll>ans;
for(auto [x,y]:vis){
if(x<1)continue;
while(y>0){
y--;
ans.push_back(x);
}
}
cout<<ans.size()<<endl;
for(auto x:ans)cout<<x<<" ";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|