A:
Who can make mistakes twice, it must be you
- There can only be at most two different numbers in the sequence
- If it is a number, pass
- If it is two numbers, the difference between their numbers must not be greater than 1
#include<bits/stdc + + .h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define x first
#define y second
int const mod1=998244353;
int const mod2=1e9 + 7;
int const N=1e5 + 50;
int const INF=0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
int a[150]={0};
set<int> b;
for(int i=1; i<=n; i + + ) {
cin >> a[i];
b.insert(a[i]);
}
if(b.size() == 1) {
cout << "YES" << "\\
";
}
else if(b.size() == 2) {
int cnt = 0;
int res = a[1];
for(int i=1; i<=n; i + + ) {
if(a[i]==res) cnt + + ;
}
if(n%2==0 & amp; & amp; cnt == n/2) cout << "YES" << "\\
";
else if(n%2!=0 & amp; & amp; (cnt == n/2 || cnt == n/2 + 1)) cout << "YES" << "\\
\ ";
else cout << "NO" << "\\
";
}
else {
cout << "NO" << "\\
";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}
B
- Is s itself legal? Legal yes
- s is illegal, t is illegal, or t is legal but both ends are not equal, no
- For all illegal positions of s, the corresponding values should be inconsistent with the two ends of t.
#include<bits/stdc + + .h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define x first
#define y second
int const mod1=998244353;
int const mod2=1e9 + 7;
int const N=1e5 + 50;
int const INF=0x3f3f3f3f;
void solve()
{
int n,m;
cin >> n >> m;
string s,t;
cin >> s;
cin >> t;
int need1 = 0;
int need2 = 0;
int give1 = 1;
int give2 = 0;
for(int i=1; i<n; i + + ) {
if(s[i-1] == s[i] & amp; & amp; s[i-1] == '0') need1 = 1;
else if(s[i-1] == s[i] & amp; & amp; s[i-1] == '1') need2 = 1;
}
for(int i=1; i<m; i + + ) {
if(t[i-1] == t[i]) {
give1 = 0;
break;
}
}
if(t[0] == t[m-1] & amp; & amp; t[0] == '0') give2 = 2;
else if(t[0] == t[m-1] & amp; & amp; t[0] == '1') give2 = 1;
\t
if(!need1 & amp; & amp; !need2) cout << "YES" << "\\
";
else if(need1 & amp; & amp; need2) cout << "NO" << "\\
";
else {
if(need1 & amp; & amp; give1 & amp; & amp; give2 == 1) cout << "YES" << "\\
";
else if(need2 & amp; & amp; give1 & amp; & amp; give2 == 2) cout << "YES" << "\\
";
else cout << "NO" << "\\
";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}
C(Supplement)
-
It doesn’t work if n is an odd number or the number of 0s and 1s in the sequence is not equal.
-
If they are both 0, add 01
r + =2after the latter 0 -
If both are 1, add 01
r + =2before the former 1 -
If they are not the same, the pointer moves to the middle
l + +,r-- -
variable
lhead pointer,rtail pointer
#include<bits/stdc + + .h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define x first
#define y second
int const mod1=998244353;
int const mod2=1e9 + 7;
int const N=2e5 + 50;
int const INF=0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
\t
int cnt_0 = count(s.begin(),s.end(),'0');
int cnt_1 = n - cnt_0;
if(n %2 != 0 || (cnt_0 != cnt_1)) {
cout << "-1" << "\\
";
return;
}
int l = 0;
int r = n - 1;
int a[500]={0};
int cnt = 0;
string t = "01";
\t
while(l<r) {
if(s[l]==s[r] & amp; & amp; s[l] == '0') {
cnt + + ;
a[cnt] = r + 1;
\t\t\t
s.insert(r + 1,t);
r + = 2;
}
else if(s[l]==s[r] & amp; & amp; s[l] == '1') {
cnt + + ;
a[cnt] = l;
\t\t\t
s.insert(l,t);
r + = 2;
}
else {
l + + ;
r --;
}
}
if(cnt == 0) {
cout << "0" << "\\
";
cout << "\\
";
return;
}
else {
cout << cnt << "\\
";
for(int i=1; i<=cnt; i + + ) cout << a[i] << " ";
cout << "\\
";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}
D (supplement)
Thinking is not easy
- Given n nodes and the people living in the n nodes, for the node
a
i
a_i
ai? and
a
j
a_j
aj? , the condition for establishing an edge is that for
S
S
The sum of the number of people in S (all nodes connected by these two nodes) is greater than
i
?
j
?
c
i*j*c
i?j?c , that is, the following formula
∑
k
∈
S
a
k
≥
i
?
j
?
c
,
\sum_{k \in S} a_k \ge i\cdot j \cdot c,
k∈S∑?ak?≥i?j?c,
- From the formula, we can see that node 1 is definitely the easiest node to establish, that is, a node can communicate with other
i
>
1
i>1
If a node with i>1 is connected, it must also be connected with node 1. Therefore, the condition for whether a strongly connected undirected graph can actually be formed is whether each node can be connected with node 1.
- So for node 1 and other nodes, we first connect the nodes that are easy to connect, that is
(
a
i
?
i
?
1
?
c
)
(a_i-i*1*c)
(aii?1?c) Bigger is better (sort)
- Traversing node 2 – node n, if connections can be established, a strongly connected undirected graph can be constructed, but not vice versa.
#include<bits/stdc + + .h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PII;
#define x first
#define y second
int const mod1=998244353;
int const mod2=1e9 + 7;
int const N=2e5 + 50;
int const INF=0x3f3f3f3f;
ll n,c;
void solve()
{
\t
cin >> n >> c;
llx;
cin >> x; //first
vector<PII> a;
l y;
\t
for(int i=2; i<=n; i + + ) {
cin >> y;
a.push_back({y,i});
}
\t
sort(a.begin(),a.end(),[](const PII & amp;x, const PII & amp;y) {
return x.first-x.second*c > y.first-y.second*c;
});
\t
bool find = true;
for(auto b : a) {
if(b.first + x < b.second * c) {
find = false;
break;
}
else x = x + b.first;
}
if(find) cout << "YES" << "\\
";
else cout << "NO" << "\\
";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}