A. Simple Palindrome
aeiou，如果这里后面+u则会多出2，+o则会多3，通过分析加相同的字母比加之前存在的不同字母赚
发现同一个太多了，又会增太大，遂平均分配，使增多幅度上升的缓慢
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll j=n/5;
ll u=n%5;
string f="aeiou";
for(ll i=0;i<=4;i++)
{
ll cnt=j;
while(cnt>0)
{
cnt--;
cout<<f[i];
}
if(i<=u-1)
{
cout<<f[i];
}
}
cout<<endl;
}
}
B1,B2.The Strict Teacher
道理都一样，最左或最右直接看相近老师位置。否则，老师就左右夹击，考虑距离除二加细节处理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
if(y==0)
return x;
else
return gcd(y,x%y);
}
ll a[200000];
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m,q;
cin>>n>>m>>q;
for(ll i=1;i<=m;i++)cin>>a[i];
sort(a+1,a+1+m);
while(q--)
{
ll x;
cin>>x;
if(x>a[m])
{
cout<<n-x+x-a[m]<<endl;
}
else if(x<a[1])
{
cout<<a[1]-x+x-1<<endl;
}
else
{
ll k=upper_bound(a+1,a+1+m,x)-a;
cout<<(a[k]-a[k-1])/2<<endl;
}
}
}
}
C.Lazy Narek
线性dp，注意之前的先记录下，防止覆盖
//旧数组要自己手动保留，否则会被覆盖
#include<iostream>
#include<string.h>
#include<map>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
string f[5000];
ll a[200000];
ll b[10];
ll c[10];
ll d[10];
ll e[10];
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n, m;
cin >> n >> m;
string k = "narek";
map<char, ll>q;
for (ll o = 0; o < 5; o++)
{
q[k[o]]++;
}
for (ll i = 0; i <= 5; i++)b[i] = 0;
for (ll i = 0; i <= 5; i++)c[i] = 0;
for (ll i = 1; i <= n; i++)
{
cin >> f[i];
}
for (ll i = 1; i <= n; i++)
{
for(ll u=0;u<=4;u++)
{
e[u]=b[u];
d[u]=c[u];
}
for (ll u = 0; u <= 4; u++)//模拟前面的头
{
if (e[u] == 0)
continue;
else
{
ll ans = 0;
ll cnt = u;
ll op = 0;
for (ll j = 0; j <m; j++)
{
if (f[i][j] == k[cnt])
{
cnt++;
if (cnt == 5)
{
ans++;
cnt = 0;
}
}
else
{
if (q[f[i][j]] > 0)
{
op++;
}
}
}
if (b[cnt] == 0)
{
b[cnt] = 1;
c[cnt] = d[u] + u + ans * 5 - op - cnt;
}
else
{
c[cnt] = max(c[cnt], d[u] + u + ans * 5 - op - cnt);
}
}
}
ll cnt = 0;
ll ans = 0;
ll op = 0;
for (ll j = 0; j < m; j++)
{
if (f[i][j] == k[cnt])
{
cnt++;
if (cnt == 5)
{
ans++;
cnt = 0;
}
}
else
{
if (q[f[i][j]] > 0)
{
op++;
}
}
}
if (b[cnt] == 0)
{
b[cnt] = 1;
c[cnt] = ans * 5 - op - cnt;
}
else
{
c[cnt] = max(c[cnt], ans * 5 - op - cnt);
}
}
ll ans = 0;
for (ll i = 0; i <= 4; i++)
{
ans = max(ans, c[i]);
}
cout << ans << endl;
}
}
D.Alter the GCD
参考了别人的代码，出处不在此，但是都源于jly。
一个数组的gcd可能个数为logn
先求前缀gcd和后缀gcd数组
遂先记录前缀gcd相同的最后一个位置
然后考虑枚举右边界，中间的[i,r]的可能个数为也为logn
然后也纪律中间数组gcd相同的最后一个位置，然后枚举这些点就好了，nlognlogn
不得不说，写的很妙，想了两天才理解为何这样做，如何维护中间数组
//维护4个log点
#include<iostream>
#include<string.h>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
ll ksm(ll x, ll y)
{
ll ans = 1;
while (y)
{
if (y & 1)
ans *= x;
x *= x;
y >>= 1;
}
return ans;
}
struct s
{
ll x, y;
};
ll a[N], b[N], prea[N], preb[N], sua[N], sub[N];
s fa[N], fb[N], pa[N], pb[N];
int main()
{
fio();
ll t; cin >> t;
while (t--)
{
ll n; cin >> n;
for (ll i = 1; i <= n; i++)cin >> a[i];
for (ll i = 1; i <= n; i++)cin >> b[i];
sua[n + 1] = sub[n + 1] = 0;
for (ll i = 1; i <= n; i++)//[1,n]
{
prea[i] = gcd(prea[i - 1], a[i]);
preb[i] = gcd(preb[i - 1], b[i]);
ll z = n - i + 1;
sua[z] = gcd(sua[z + 1], a[z]);
sub[z] = gcd(sub[z + 1], b[z]);
}
ll cnt1=0, cnt2 = 0;
for (ll i = 0; i <= n + 1; i++)//维护最后一个没有变化的gcd
{
if (i == n + 1 || prea[i] != prea[i + 1])
{
cnt1++;
pa[cnt1] = { prea[i],i+1 };
}
if (i == n + 1 || preb[i] != preb[i + 1])
{
cnt2++;
pb[cnt2] = { preb[i],i+1 };
}
}
ll ans = 0, cnt = 0;
ll l = 0, r1 = 0;//左权值，右位置
for (ll r = 1; r <= n; r++)//相当于选择什么右边界
{
ll k = 0;
for (ll i = 1; i <= l; i++)//先更新
{
ll t = gcd(a[r], fa[i].x); fa[i].x = t;
}
for (ll i = 1; i <= l; i++)//后维护
{
if (k > 0 && fa[k].x == fa[i].x)
{
fa[k].y = fa[i].y;
}
else
{
k++;
fa[k] = fa[i];
}
}
l = k; l++; fa[l] = { a[r],r };
k = 0;
for (ll i = 1; i <= r1; i++)
{
ll t = gcd(b[r], fb[i].x); fb[i].x = t;
}
for (ll i = 1; i <= r1; i++)
{
if (k > 0 && fb[k].x == fb[i].x)
{
fb[k].y = fb[i].y;
}
else
{
k++;
fb[k] = fb[i];
}
}
r1 = k; r1++; fb[r1] = { b[r],r };
ll pa1 = 1, fa1 = 1, pb1 = 1, fb1 = 1;
ll lst = 0;
while (1)
{
ll u = min(min(pa[pa1].y, pb[pb1].y), min(fa[fa1].y, fb[fb1].y));
ll t = gcd(pa[pa1].x, gcd(fb[fb1].x, sua[r + 1])) + gcd(pb[pb1].x, gcd(fa[fa1].x, sub[r + 1]));
if (t > ans)
{
ans = t, cnt = u - lst;
}
else if (ans == t)
{
cnt += u - lst;
}
if (u == r)break;
lst = u;
if (pa[pa1].y == u)pa1++;
if (pb[pb1].y == u)pb1++;
if (fa[fa1].y == u)fa1++;
if (fb[fb1].y == u)fb1++;
}
}
cout << ans << " " << cnt << endl;
}
}