Hope you enjoy those tasks!
Tutorial
Solution(python by pikmike)
Solution(C++)
Tutorial
Solution(python by pikmike)
Tutorial is loading...
from sys import stdin
t = int(stdin.readline())
for _ in range(t):
n, k = map(int, stdin.readline().split())
s = stdin.readline()
cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]
for i in range(n):
cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1
ans = 0
for i in range(k // 2):
ans += 2 * n // k - max(cnt[i])
if k % 2 == 1:
ans += n // k - max(cnt[k // 2])
print(ans)
#include<bits/stdc++.h>
using namespace std;
const int maxn=200007;
int n,k,ans=0;
int cnt[maxn][26];
string s;
int differ(int u,int v){
int ret=0,mx=0;
for (int j=0;j<26;++j){
ret+=cnt[u][j]+cnt[v][j];
mx=max(mx,cnt[u][j]+cnt[v][j]);
}
return ret-mx;
}
int main(){
int t;
cin>>t;
while (t--){
cin>>n>>k>>s;
for (int i=0;i<k;++i){
for (int j=0;j<26;++j){
cnt[i][j]=0;
}
}
for (int i=0;i<n;++i){
cnt[i%k][s[i]-'a']++;
}
int ans=0;
for (int i=0;i<k;++i){
ans+=differ(i,k-1-i);
}
cout<<ans/2<<"\n";
}
return 0;
}
Idea: adedalic
Tutorial is loading...
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
vector<int> p, c;
inline bool read() {
if(!(cin >> n))
return false;
p.resize(n);
c.resize(n);
fore(i, 0, n) {
cin >> p[i];
p[i]--;
}
fore(i, 0, n)
cin >> c[i];
return true;
}
inline void solve() {
vector<int> used(n, 0);
int ans = INF;
fore(st, 0, n) {
if(used[st])
continue;
vector<int> cycle;
int v = st;
while(!used[v]) {
used[v] = 1;
cycle.push_back(v);
v = p[v];
}
fore(step, 1, sz(cycle) + 1) {
if(sz(cycle) % step != 0)
continue;
fore(s, 0, step) {
bool eq = true;
for(int pos = s; pos + step < sz(cycle); pos += step) {
if(c[cycle[pos]] != c[cycle[pos + step]])
eq = false;
}
if(eq) {
ans = min(ans, step);
break;
}
}
}
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: adedalic
Tutorial is loading...
MOD = 998244353
p = [1] * 200005
for i in range(1, 200005):
p[i] = (p[i - 1] * 10) % MOD
n = int(input())
for i in range(1, n):
res = 2 * 10 * 9 * p[n - i - 1]
res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
print(res % MOD, end = ' ')
print(10)
Idea: Neon
Tutorial is loading...
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef pair<int, int> pt;
const int MOD = 998244353;
const int N = 500 * 1000 + 13;
int n, k, m;
pair<pt, int> q[N];
int ones[N];
int mx[N], sum[N];
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
return x;
}
int calc(int t) {
memset(ones, 0, sizeof(ones));
memset(mx, -1, sizeof(mx));
forn(i, m) {
int l = q[i].x.x, r = q[i].x.y;
if (q[i].y & (1 << t)) {
ones[l]++;
ones[r + 1]--;
} else {
mx[r] = max(mx[r], l);
}
}
int j = -1;
forn(i, n) {
int cur = 0;
if (!ones[i]) {
cur = sum[i];
if (j == -1) cur = add(cur, 1);
else cur = add(cur, -sum[j]);
}
sum[i + 1] = add(sum[i], cur);
ones[i + 1] += ones[i];
j = max(j, mx[i]);
}
return add(sum[n], j != -1 ? -sum[j] : 1);
}
int main() {
scanf("%d%d%d", &n, &k, &m);
forn(i, m) {
scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
--q[i].x.x; --q[i].x.y;
}
int ans = 1;
forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
printf("%d\n", ans);
}
1327G - Letters and Question Marks
Idea: BledDest
Tutorial is loading...
#include<bits/stdc++.h>
using namespace std;
const int N = 8000043;
const int K = 15;
const int M = 1043;
int k;
char buf[N], buf2[M];
vector<string> t;
vector<int> c;
string s;
map<char, int> nxt[M];
int lnk[M];
int p[M];
char pchar[M];
map<char, int> go[M];
int term[M];
int ts = 1;
int A[M][K];
int F[M][K];
int dp[M];
int get_nxt(int x, char c)
{
if(!nxt[x].count(c))
{
p[ts] = x;
pchar[ts] = c;
nxt[x][c] = ts++;
}
return nxt[x][c];
}
void add_string(int i)
{
int cur = 0;
for(auto x : t[i])
{
cur = get_nxt(cur, x);
}
term[cur] += c[i];
}
int get_go(int x, char c);
int get_lnk(int x)
{
if(lnk[x] != -1)
return lnk[x];
if(x == 0 || p[x] == 0)
return lnk[x] = 0;
return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
}
int get_dp(int x)
{
if(dp[x] != -1)
return dp[x];
dp[x] = term[x];
if(get_lnk(x) != x)
dp[x] += get_dp(get_lnk(x));
return dp[x];
}
int get_go(int x, char c)
{
if(go[x].count(c))
return go[x][c];
if(nxt[x].count(c))
return go[x][c] = nxt[x][c];
if(x == 0)
return go[x][c] = 0;
return go[x][c] = get_go(get_lnk(x), c);
}
void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
{
sA = vector<int>(ts);
for(int i = 0; i < ts; i++)
sA[i] = i;
sF = vector<long long>(ts);
for(auto c : s)
{
int ci = int(c - 'a');
for(int i = 0; i < ts; i++)
{
sF[i] += F[sA[i]][ci];
sA[i] = A[sA[i]][ci];
}
}
}
long long solve(const string& s)
{
long long BAD = (long long)(-1e18);
vector<int> pos;
for(int i = 0; i < s.size(); i++)
if(s[i] == '?')
pos.push_back(i);
int cntQ = pos.size();
vector<vector<int> > skip_A(cntQ + 1);
vector<vector<long long> > skip_F(cntQ + 1);
build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
for(int i = 1; i < cntQ; i++)
build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);
vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
vector<int> used(1 << K);
dp[0][skip_A[0][0]] = skip_F[0][0];
queue<int> q;
q.push(0);
used[0] = 1;
long long ans = BAD;
while(!q.empty())
{
int k = q.front();
q.pop();
int step = __builtin_popcount(k);
if(step == cntQ)
{
for(int i = 0; i < ts; i++)
ans = max(ans, dp[k][i]);
continue;
}
for(int i = 0; i < K - 1; i++)
{
if(k & (1 << i)) continue;
int nk = (k ^ (1 << i));
if(used[nk] == 0)
{
used[nk] = 1;
q.push(nk);
}
for(int j = 0; j < ts; j++)
{
if(dp[k][j] == BAD)
continue;
int nj = get_go(j, char('a' + i));
int newSt = skip_A[step + 1][nj];
long long add = get_dp(nj) + skip_F[step + 1][nj];
dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
}
}
}
return ans;
}
int main()
{
scanf("%d", &k);
t.resize(k);
c.resize(k);
for(int i = 0; i < k; i++)
{
scanf("%s %d", buf2, &c[i]);
t[i] = buf2;
}
scanf("%s", buf);
s = buf;
for(int i = 0; i < k; i++)
add_string(i);
for(int i = 0; i < ts; i++)
{
lnk[i] = -1;
dp[i] = -1;
}
for(int i = 0; i < ts; i++)
{
get_lnk(i);
for(char c = 'a'; c <= 'o'; c++)
get_go(i, c);
}
for(int i = 0; i < ts; i++)
get_dp(i);
for(int i = 0; i < ts; i++)
{
for(int j = 0; j < K; j++)
{
A[i][j] = get_go(i, char('a' + j));
F[i][j] = dp[A[i][j]];
}
}
int n = s.size();
vector<int> leftQ(n, -1);
vector<int> rightQ(n, -1);
for(int i = 0; i < n; i++)
{
if(i != 0)
leftQ[i] = leftQ[i - 1];
if(s[i] == '?')
leftQ[i] = i;
}
for(int i = n - 1; i >= 0; i--)
{
if(i != n - 1)
rightQ[i] = rightQ[i + 1];
if(s[i] == '?')
rightQ[i] = i;
}
vector<int> bad(n, 0);
if(leftQ.back() == -1)
bad = vector<int>(n, 1);
long long ans = 0;
int curSt = 0;
string news = "";
for(int i = 0; i < n; i++)
{
int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
if(bad[i])
ans += F[curSt][ci];
curSt = A[curSt][ci];
if(!bad[i])
news.push_back(s[i]);
else if(i != 0 && !bad[i - 1])
news.push_back('o');
}
if(!news.empty())
ans += solve(news);
printf("%lld\n", ans);
}