Codeforces Round #579 (div3)
Codeforces Round #579 (div3)
A
由于数据范围很小，我们可以直接枚举每个点，然后在向两边遍历去匹配
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t --)
{
int n;
cin >> n;
int a[300];
for(int i = 0; i < n; i ++)
cin >> a[i];
bool flag = false;
for(int i = 0; i < n; i ++)
{
int cnt = 1;
while(cnt < n)
{
if(a[(i - cnt + 1 + n) % n] != cnt)
break;
cnt ++;
}
if(cnt == n)
{
flag = true;
break;
}
cnt = 1;
while(cnt < n)
{
if(a[(i + cnt - 1 + n) % n] != cnt)
break;
cnt ++;
}
if(cnt == n)
{
flag = true;
break;
}
}
if(flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
//system("pause");
}
B
给了4*n个木棍，去组成n个面积相同的矩形，我们分析可以知道，每种长度的木棍肯定是偶数个。然后发现，由最短木棍跟最长木棍组成的矩形就是我们需要的矩形。类似首尾各取一个。
这样我们就可以对这个矩形的面积进行因式分解，对于每一对约数，如果都是已知长度木棍且数量相等，这样就可以组成相应的矩形，将这一对约数的木棍的数量设为零。这样最后在检查一遍，如果存在木棍数量不为零，即不能成立。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e4 + 5;
int num[N];
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t --)
{
int n;
cin >> n;
ll a[1000] = {0};
memset(num, 0, sizeof(num));
for(int i = 0; i < 4 * n; i ++)
{
cin >> a[i];
num[a[i]] ++;
}
bool flag = false;
for(int i = 0; i < 4 * n; i ++)
{
if(num[a[i]] & 1)
{
flag = true;
break;
}
}
sort(a, a + 4 * n);
ll ans = a[0] * a[4 * n - 1];
for(ll i = 1; i * i <= ans; i ++)
{
if(ans % i == 0)
{
if(i > 10000 || (ans / i) > 10000)
continue;
if(num[i] == 0 && num[ans / i] == 0)
continue;
if(num[i] != 0 && num[ans / i] != 0)
{
int dd = min(num[i], num[ans / i]);
num[i] -= dd;
if(i != ans / i)
num[ans / i] -= dd;
}
}
}
for(int i = 0; i < 4 * n; i ++)
{
if(num[a[i]] != 0)
{
flag = true;
break;
}
}
if(!flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
//system("pause");
}
C
题目让我们找可以整除所有ai的数的数量。
第一眼我们肯定想到了给所有ai求一个gcd, 然后对这个gcd求一下其约数个数，然后就发现，可以过了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 4e5 + 5;
ll a[N];
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
if(n == 1)
{
ll ans = 1;
for(ll i = 2; i * i <= a[0]; i ++)
{
if(a[0] % i == 0)
{
ll d = 0;
while(a[0] % i == 0)
{
d ++;
a[0] /= i;
}
ans = ans * (d + 1);
}
}
if(a[0] != 1)
ans *= 2;
cout << ans << endl;
return 0;
}
ll gcd = __gcd(a[0], a[1]);
for(int i = 2; i < n; i ++)
{
gcd = __gcd(gcd, a[i]);
}
if(gcd == 1)
{
cout << 1 << endl;
return 0;
}
ll ans = 1;
for(ll i = 2; i * i <= gcd; i ++)
{
if(gcd % i == 0)
{
ll d = 0;
while(gcd % i == 0)
{
d ++;
gcd /= i;
}
ans = ans * (d + 1);
}
}
if(gcd != 1)
{
ans *= 2;
}
cout << ans << endl;
}
D1&D2(后补)
d1和d2的区别也就是d1的数据范围很小
对于文本串s跟模式串t，我们可以维护一个前缀跟一个后缀，维护t在s的前缀或者后缀中匹配的数量，然后我们在枚举区间[i,j)，判断[0,i - 1]和[j, n - 1]，如果两个区间匹配t的数量大于等于t的长度，那么就可以记录一下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 5;
int suf[N], pre[N];
int main()
{
//freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
string s, t;
cin >> s >> t;
memset(pre, 0, sizeof(pre));
memset(suf, 0, sizeof(suf));
int cnt = 0, len_s = s.length(), len_t = t.length();
for(int i = 0; i < len_s; i ++)
{
if(cnt < len_t && s[i] == t[cnt])
{
pre[i] = cnt + 1;
cnt ++;
}
else
pre[i] = pre[i - 1];
}
cnt = len_t - 1;
for(int i = len_s - 1; i >= 0; i --)
{
if(cnt >= 0 && s[i] == t[cnt])
{
suf[i] = len_t - cnt;
cnt --;
}
else
suf[i] = suf[i + 1];
}
int ans = 0, j = 0;
for(int i = 0; i < len_s; i ++)
{
if(i == 0)
{
while(j <= len_s && suf[j] >= len_t)
{
ans = max(ans, j - i);
j ++;
}
}
else
{
while(j <= len_s && pre[i - 1] + suf[j] >= len_t)
{
ans = max(ans, j - i);
j ++;
}
}
}
cout << ans << endl;
}
E
对于一个序列，我们需要维护其序列内不同数的数量。我们可以从前往后和从后往前跑两边。从后往前，优先考虑加一,从前往后，优先考虑减一
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 150000 + 5;
int a[N];
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
sort(a, a + n);
a[n - 1] ++;
for(int i = n - 2; i >= 0; i --)
{
if(i != 0 && a[i] == a[i + 1] && a[i] == a[i - 1])
continue;
if(a[i + 1] - a[i] > 1)
a[i] ++;
//else if(i != 0 && a[i] - a[i - 1] > 1)
//a[i] --;
}
if(a[0] > 1)
a[0] --;
for(int i = 1; i < n; i ++)
{
if(i != n - 1 && a[i] == a[i + 1] && a[i] == a[i - 1])
continue;
if(a[i] - a[i - 1] > 1)
a[i] --;
//else if(i != n - 1 && a[i + 1] - a[i] > 1)
//a[i] ++;
}
ll ans = 1;
for(int i = 1; i < n; i ++)
if(a[i] != a[i - 1])
ans ++;
cout << ans << endl;
//system("pause");
}
查看12道真题和解析