小寄() \(100+0+100+25\) \(rk9\)
\(T4\) 没开 \(long\ long\) 挂 \(25pts\) 实属不该
T1
当时看到字符串差点给跳过了() 结果是呆呆签到题
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mid (l+r>>1)
#define inl inline
#define eb emplace_back
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
const int N = 1e5 + 5;
//char buf[1<<24] , *p1 , *p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
#define getchar() cin.get();
int read()
{
int x = 0 , f = 1;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f ;
}
int n , m , ans[N] , a[N] , b[N];
string s1 , s2;
signed main ()
{
freopen ( "love.in" , "r" , stdin );
freopen ( "love.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , m = read();
cin >> s1; cin >> s2;
while ( s2.size() < n ) s2 = s2 + s2;
for ( int i = 1 ; i <= n ; i ++ ) a[i] = s1[i-1] - 'a' + 1 , b[i] = s2[i-1] - '0';
for ( int i = 1 ; i <= n ; i ++ ) ans[i] = a[i] + b[i];
for ( int i = 1 ; i <= n ; i ++ )
cout << (ans[i]>26?(char)(ans[i]-26+'a'-1):(char)(ans[i]+'a'-1));
cout << endl;
return 0;
}
T2
博弈论 但是\(skip\)
T3
可以显然发现每一条重链的贡献就是重链的树高+轻链的贡献最大值
\(dp\) 即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mid (l+r>>1)
#define inl inline
#define eb emplace_back
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
#define print(x) cout << #x << ' ' << x << endl
const int N = 1e7 + 5;
char buf[1<<24] , *p1 , *p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
//#define getchar() cin.get();
int read()
{
int x = 0 , f = 1;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f ;
}
int n , t[N] , fa[N] , son[N] , top[N] , len[N] , lg[N];
//vector<int>e[N];
//inl void add ( int u , int v ) { e[u].eb(v); }
int head[N] , cnt;
struct node { int to , nxt; } e[N];
inl void add ( int u , int v ) { e[++cnt] = { v , head[u] } , head[u] = cnt; }
void dfs2 ( int u , int tp , int &sz )
{
// cout << u << ' ' << tp << ' ' << sz << endl;
// cout << son[u] << endl;
top[u] = tp , sz ++;
if ( son[u] ) dfs2 ( son[u] , tp , sz );
for ( int i = head[u] ; i ; i = e[i].nxt ) { int v = e[i].to; if ( v != fa[u] && v != son[u] ) dfs2 ( v , v , len[v] ); }
}
void dfs ( int u , int f )
{
for ( int i = head[u] ; i ; i = e[i].nxt )
{
int v = e[i].to;
if ( v ^ f )
{
dfs ( v , u );
t[u] = max ( t[u] , t[v] );
}
}
if ( top[u] == u ) t[u] += lg[len[u]];
}
signed main ()
{
freopen ( "aqua.in" , "r" , stdin );
freopen ( "aqua.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read();
lg[0] = -1;
for ( int i = 1 ; i <= n ; i ++ ) lg[i] = lg[(int)ceil((double)i/2)] + 1;
// for ( int i = 1 ; i <= 16 ; i ++ ) cout << (int)ceil(log2(i))+1 << endl;
// for ( int i = 1 ; i <= 16 ; i ++ ) cout << lg[i] << endl;
for ( int i = 1 ; i <= n ; i ++ ) fa[i] = read() , add ( fa[i] , i );
for ( int i = 1 ; i <= n ; i ++ ) son[i] = read();
dfs2 ( 1 , 1 , len[1] );
// for ( int i = 1 ; i <= n ; i ++ ) print(len[i]) , print((top[i]==i));
dfs ( 1 , 0 );
cout << t[1] << endl;
return 0;
}
T4
\(50pts\) 就是维护差分数组和正常数组 区间修改区间(单点)查询即可
正解是 我们将第一个点(也就是 \((0,1)\) 这个点)赋值为 \(1\) 先递推出来整个矩阵
考虑在第 \(i\) 个位置上的修改 值为 \(val\) 的影响 最后的影响就是矩阵向右移动一个定长再乘上 \(val\)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define mid (l+r>>1)
#define inl inline
#define eb emplace_back
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pii pair<int,int>
#define print(x) cout<<#x<<' '<<x<<endl
#define int long long
const int K = 100 + 5;
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
//char buf[1<<24] , *p1 , *p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
#define getchar() cin.get();
int read()
{
int x = 0 , f = 1;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f ;
}
int n , m , k , a[K][N] , pos[N] , val[N] , cnt;
int solve ( int x )
{
int res = 0;
for ( int i = 1 ; i <= cnt ; i ++ )
if ( pos[i] <= x ) ( res += a[k][x-pos[i]+1] * val[i] ) %= mod;
return res;
}
signed main ()
{
// freopen ( "ruby.in" , "r" , stdin );
// freopen ( "ruby.out" , "w" , stdout );
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
n = read() , m = read() , k = read();
a[0][1] = 1;
for ( int i = 1 ; i <= k ; i ++ )
for ( int j = 1 ; j <= n ; j ++ )
a[i][j] = ( a[i-1][j] + a[i][j-1] ) % mod;
for ( int i = 1 , x , y ; i <= m ; i ++ )
{
int op = read();
if ( op == 0 ) x = read() , y = read() , pos[++cnt] = x , val[cnt] = y;
else x = read() , cout << solve(x) << endl;
}
return 0;
}