Codeforces Round #579 (Div. 3)
http://codeforces.com/contest/1203
-------------------------------------------------
赛后两分钟，在F1后面加了一个判断，过了。。少了一题血亏
从左往右，从右往左扫一遍
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
int a[205];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
for (int i = 0; i < n; i++)
sc("%d", &a[i]);
for (int i = n; i <= 2 * n; i++)
a[i] = a[i - n];
for (int i = 0; i < n; i++)
{
for (int j = i; j < i + n; j++)
{
if (a[j] != j - i + 1)
goto qwe;
}
printf("YES\n");
goto qq;
qwe:;
}
for (int i = 2 * n - 1; i >= n; i--)
{
for (int j = i; j > i - n; j--)
{
if (a[j] != i - j + 1)
goto qwe1;
}
printf("YES\n");
goto qq1;
qwe1:;
}
pr("NO\n");
qq:;
qq1:;
}
} 每两个作为一份，然后要相等的话 前面*后面 一定是相等的面积。
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
int num[10005];
int main()
{
int T, t;
sc("%d", &T);
while (T--)
{
memset(num, 0, sizeof(num));
vector<int>v;
int n, f, len;
sc("%d", &n);
n *= 4;
for (int i = 1; i <= n; i++)
{
sc("%d", &t);
num[t]++;
}
for (int i = 1; i <= 10000; i++)
{
while (num[i] >= 2)
{
v.push_back(i);
num[i] -= 2;
}
if (num[i] == 1)
{
printf("NO\n");
goto qwe;
}
}
len = v.size();
if (len & 1)
{
printf("NO\n");
goto qwe;
}
f = v[0] * v[len - 1];
for (int i = 0; i < len / 2; i++)
{
if (v[i] * v[len - 1 - i] != f)
{
printf("NO\n");
goto qwe;
}
}
printf("YES\n");
qwe:;
}
} 最大公因数的因子个数，写错了一个变量WA了一次
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int n;
scanf("%d", &n);
ll t1, t2;
sc("%lld", &t1);
for (int i = 1; i < n; i++)
{
sc("%lld", &t2);
t1 = gcd(t1, t2);
}
ll qq = sqrt(t1);
ll ans = 0;
for (ll i = 1; i <= qq; i++)
{
if (t1 % i == 0)
{
ans++;
if (t1 / i != i)
ans++;
}
}
printf("%lld", ans);
} D1 - Remove the Substring (easy version)
给两个串，已知第二个串是第一个串的子序列，要在第一个串上删除一个子串，使得第二个串还是第一个串的子串
D1 做法：暴力枚举答案，然后顺序计算删除后的字符，暴力判断是否是他的子序列
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool judge(string q, string w)
{
int lenq = q.size();
int lenw = w.size();
int f = 0;
for (int i = 0; i < lenq; i++)
{
if (f >= lenw)
break;
if (q[i] == w[f])
{
f++;
}
}
if (f >= lenw)
return true;
else
return false;
}
string s1, s2;
int main()
{
ios::sync_with_stdio(false);
cin >> s1 >> s2;
int len1 = s1.size();
int len2 = s2.size();
for (int i = len1 - len2; i >= 0; i--)
{
for (int j = 0; j <= len1 - i; j++)
{
string s;
for (int k = 0; k < j; k++)
s += s1[k];
for (int k = j + i; k < len1; k++)
s += s1[k];
if (judge(s, s2))
{
printf("%d\n", i);
return 0;
}
}
}
} D2 - Remove the Substring (hard
D2做法：假设第一个串长度是len1，第二个串长度是len2，删除之后还要是他的子串，那么对于第二个串的两个相邻的字符来说，最多删除的肯定是 第一个字符的最左满足的位置 到 第二个字符最右满足的位置。
所以我们预处理最左满足子序列是第二个串的每个字符的位置和最右满足的字符位置。
预处理一下头尾，然后遍历一遍，就可以AC。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s1[200005], s2[200005];
int pre[200005], nex[200005];
int main()
{
sc("%s%s", s1, s2);
int len1 = strlen(s1);
int len2 = strlen(s2);
int f = 0;
for (int i = 0; i < len1; i++)
{
if (s1[i] == s2[f])
{
pre[f] = i;
f++;
}
if (f >= len2)
break;
}
f = len2 - 1;
for (int i = len1 - 1; i >= 0; i--)
{
if (s1[i] == s2[f])
{
nex[f] = i;
f--;
}
if (f < 0)
break;
}
int ans = max(nex[0], len1 - 1 - pre[len2 - 1]);
for (int i = 1; i < len2; i++)
{
ans = max(ans, nex[i] - pre[i - 1] - 1);
}
printf("%d", ans);
} 贪心乱搞
#include <bits/stdc++.h>
using namespace std;
int n, a[1000005];
int main()
{
int ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
sort(a + 1, a + 1 + n, [](int q, int w) {
return q > w;
});
a[0] = 2e9;
for (int i = 1; i <= n; ++i)
{
if (a[i] + 1 < a[i - 1])
++a[i];
else if (a[i] < a[i - 1])
continue;
else if (a[i] == a[i - 1])
{
if (i == n)
a[i] = max(1, a[i] - 1);
else if (a[i] == a[i + 1])
continue;
else
a[i] = max(1, a[i] - 1);
}
}
for (int i = 1; i <= n; ++i)
if (a[i] != a[i - 1])
++ans;
printf("%d\n", ans);
} F1 - Complete the Projects (easy version)
先将所有 b 大于0的选来，然后按照a+b排序（待证明），依此选，能选完就 YES ，否则 NO。
#include <bits/stdc++.h>
#define Pair pair<int,int>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
vector<Pair>v,zhen;
int main()
{
int n, s, a, b;
sc("%d%d", &n, &s);
for (int i = 0; i < n; i++)
{
sc("%d%d", &a, &b);
if (b >= 0)
{
zhen.push_back(Pair{ a,b });
}
else
v.push_back(Pair{ a,b });
}
sort(zhen.begin(), zhen.end(), [](Pair q, Pair w) {
return q.first < w.first;
});
int len1 = zhen.size();
for (int i = 0; i < len1; i++)
{
if (s >= zhen[i].first)
{
s += zhen[i].second;
}
else
{
printf("NO\n");
return 0;
}
}
sort(v.begin(), v.end(), [](Pair q, Pair w) {
if (q.first + q.second != w.first + w.second)
return q.first + q.second > w.first + w.second;
return q.first > w.first;
});
int len2 = v.size();
for (int i = 0; i < len2; i++)
{
if (s >= v[i].first)
s += v[i].second;
else
{
printf("NO\n");
return 0;
}
}
if (s >= 0)
printf("YES\n");
else
printf("NO\n");
} F2 - Complete the Projects (hard version)
同理，先把所有能取的b为正的先取了，然后和F1一样先排序，因为这里不知道应该怎么选会使的能选的物品的数量最多，考虑01背包，进行状态转移。然后取一个最大的数量。
#include <bits/stdc++.h>
#define Pair pair<int,int>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
vector<Pair>v, zhen;
ll dp[60005];
int main()
{
int n, s, a, b;
sc("%d%d", &n, &s);
for (int i = 0; i < n; i++)
{
sc("%d%d", &a, &b);
if (b >= 0)
{
zhen.push_back(Pair{ a,b });
}
else
v.push_back(Pair{ a,b });
}
sort(zhen.begin(), zhen.end(), [](Pair q, Pair w) {
return q.first < w.first;
});
int len1 = zhen.size();
int cnt = 0;
for (int i = 0; i < len1; i++)
{
if (s >= zhen[i].first && s + zhen[i].second >= 0)
{
s += zhen[i].second;
cnt++;
}
else
{
break;
}
}
sort(v.begin(), v.end(), [](Pair q, Pair w) {
if (q.first + q.second != w.first + w.second)
return q.first + q.second > w.first + w.second;
return q.first > w.first;
});
int len2 = v.size();
for (int i = 0; i < len2; i++)
{
for (int j = v[i].first; j <= s; j++)
{
if (j + v[i].second >= 0)
dp[j + v[i].second] = max(dp[j + v[i].second], dp[j] + 1);
}
}
ll maxn = 0;
for (int i = 60000; i >= 0; i--)
{
if (dp[i])
maxn = max(maxn, dp[i]);
}
printf("%lld\n", cnt + maxn);
}
查看20道真题和解析
文远知行公司福利 265人发布