A - Edge Checker 2

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

1≤a<b≤15
a and b are integers.

Input

The input is given from Standard Input in the following format:

a b

Output

Print Yes if there is a segment that directly connects the points numbered a and b; print No otherwise.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

AC Code:

#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
int a, b;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);cin >> a >> b;if (b == a * 2 || b == a * 2 + 1)puts("Yes");elseputs("No");return 0;
}

B - Longest Uncommon Prefix

思路:朴素方法

AC Code:

#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int n;string s;cin >> n >> s;for (int i = 1; i < n; i++){for (int j = 1; j <= n; j++){if (i + j > n){cout << j - 1 << "\n";break;}if (s[j - 1] == s[j + i - 1]){cout << j - 1 << "\n";break;}}}return 0;
}

C - abc285_brutmhyhiizp

AC Code:

// 简单模拟
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);string s;cin >> s;int l = s.size();long long res = 0, add = 26;for (int i = 1; i <= l - 1; i++){res += add;add *= 26;}long long num = 0;for (int i = 0; i < l; i++){num *= 26;num += (s[i] - 'A');}cout << res + num + 1;return 0;
}

F - Substring of Sorted String

AC Code:

#include<bits/stdc++.h>
using namespace std;#define lowbit(x) x&(-x)typedef long long ll;
const ll maxn=1e5+5;int n,q;char s[maxn];
int bit[30][maxn],sum[30],bit2[maxn];void add(int a[maxn],int x,int c) {for(int i=x;i<=n;i+=lowbit(i)) a[i]+=c;return ;
}int ask(int a[maxn],int x) {int res=0;for(int i=x;i>0;i-=lowbit(i)) res+=a[i];return res;
}void add2(int x,int c) {for(int i=x;i<n;i+=lowbit(i)) bit2[i]+=c;return ;
}int ask2(int x) {int res=0;for(int i=x;i>0;i-=lowbit(i)) res+=bit2[i];return res;
}int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>s+1;for(int i=1;i<=n;i++) sum[s[i]-'a']++,add(bit[s[i]-'a'],i,1);for(int i=1;i<n;i++) if(s[i]<=s[i+1]) add2(i,1);cin>>q;for(int i=1,op;i<=q;i++) {cin>>op;if(op==1) {int x;char c;cin>>x>>c;sum[s[x]-'a']--,add(bit[s[x]-'a'],x,-1);if(x<n&&s[x]<=s[x+1]) add2(x,-1);if(x>1&&s[x-1]<=s[x]) add2(x-1,-1);s[x]=c;sum[s[x]-'a']++,add(bit[s[x]-'a'],x,1);if(x<n&&s[x]<=s[x+1]) add2(x,1);if(x>1&&s[x-1]<=s[x]) add2(x-1,1);}else {int l,r;cin>>l>>r;if(ask2(r-1)-ask2(l-1)!=r-l) {cout<<"No\n";continue;}int flag=0,tot=0;for(int j=0;j<26;j++) {int num=ask(bit[j],r)-ask(bit[j],l-1);tot+=num;if(!flag&&num==0) continue;if(!flag) flag=1;else {if(num<sum[j]&&tot!=r-l+1) {flag=-1;break;}}}if(flag==-1) cout<<"No\n";else cout<<"Yes\n";}}return 0;
}