A-Clam and Fish
思维模拟
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const int maxn = 5005;
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
string s;
cin >> s;
int ans = 0, clam = 0, p = 1;
s = '0' + s;
for (int i = 1; i <= n; i++)
{
if (s[i] == '2' || s[i] == '3')ans++;
else if (s[i] == '0' && clam)ans++, clam--;
else if (s[i] == '1')
{
int j = max(i + 1, p);
for (; j <= n; j++)
{
if (s[j] == '0')
{
s[j] = '2';
p = j + 1;
break;
}
}
if (j > n)
{
if (clam)
clam--, ans++;
else
clam++;
p = n + 1;
}
}
}
cout << ans << endl;
}
return 0;
}
B-Classical String Problem
思维模拟
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const int maxn = 5005;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();
return f * x;
}
int main()
{
fastio;
string s;
cin >> s;
int t;
cin >> t;
int tmp = 0;
int len = s.length();
while (t--)
{
char o;
int x;
cin >> o >> x;
if (o == 'M')
tmp += x;
else
{
if (tmp == 0)
cout << s[x - 1] << endl;
else if (tmp > 0)
cout << s[(x + tmp - 1) % len] << endl;
else
cout << s[((len + tmp + x - 1) % len + len) % len] << endl;
}
}
return 0;
}
E-Two Matchings
贪心 DP ，打的时候真不知道这是个dp
这样我们就能以4和6一组作为状态进行dp了,最终状态肯定能被拆成数个4+数个6，否则不优
（解释：组与组之间断裂，dp寻找的就是在哪里断裂最优，然后组之间的每个差值只被计入2次答案是下界（最优），无法找到更优的连法)
状态转移方程: (dp[i] = min(dp[i], dp[i - 4] + 2 * (a[i] - a[i - 3])))
(dp[i] = min(dp[i], dp[i - 6] + 2 * (a[i] - a[i - 5]))|i >= 6)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-12;
const int inf = 1e17 + 7;
const int maxn = 1e5 + 10;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();
return f * x;
}
ll dp[maxn];
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<ll>a(n + 1), dp(n + 1, inf);
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a.begin() + 1, a.end());
dp[0] = 0;
for (int i = 4; i <= n; i++)
{
dp[i] = min(dp[i], dp[i - 4] + 2 * (a[i] - a[i - 3]));//容斥
if (i >= 6)dp[i] = min(dp[i], dp[i - 6] + 2 * (a[i] - a[i - 5]));
}
cout << dp[n] << endl;
}
return 0;
}
F-Fraction Construction Problem
构造 EXGCD 不定方程
打的时候写了个EXGCD解了下ab不互素的不定方程，然后发现不太会整其他的情况，又去想了个sb的错误做法，我只能爬
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-12;
const int maxn = 2e6 + 10;
const int inf = 1e9;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();
return f * x;
}
ll x, y;
ll v[maxn], p[maxn], cnt;
void init_e()
{
memset(v, 0, sizeof(v));
cnt = 0;
}
void Euler_sieve(int n)
{
//init_e();
cnt = 0;
for (int i = 2; i <= n; i++) {
if (v[i] == 0) { v[i] = i; p[++cnt] = i; }
for (int j = 1; j <= cnt; j++)
{
if (p[j] > v[i] || p[j] > n / i)break;
v[i * p[j]] = p[j];
}
}
}
ll exgcd(ll a, ll b, ll& x, ll& y)
{
if (!b)
{
x = 1;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int gcd(int a, int b)
{
while (b)
{
ll tmp = b;
b = a % b;
a = tmp;
}
return a;
}
int main()
{
fastio;
int t;
cin >> t;
Euler_sieve(2e6 + 5);
while (t--)
{
x = y = 0;
ll a, b;
cin >> a >> b;
ll g = gcd(a, b);
if (g != 1)
{
cout << a / g + 1 << " " << b / g << " " << 1 << " " << b / g << endl;
continue;
}
g = 1;
if (b == 1 || v[b] == b) {
cout << -1 << " " << -1 << " " << -1 << " " << -1 << endl;
continue;
}
ll k = v[b];
while (b % k == 0)
b /= k, g *= k;
if (b == 1) {
cout << -1 << " " << -1 << " " << -1 << " " << -1 << endl;
continue;
}
//cout << p << " " << b << endl;
exgcd(b, g, x, y);
if (x > 0)
cout << x * a << " " << g << " " << -y * a << " " << b << endl;
else
cout << y * a << " " << b << " " << -x * a << " " << g << endl;
}
return 0;
}
最后！！！画了一万年也没有画完的线稿来了，什么时候才能有时间画完啊QAQ
