A.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int ton[26];
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
string s;
cin>>s;
for(int i=0;i<26;i++)
ton[i] = i;
for(int i=1;i<=m;i++)
{
char x,y;
cin>>x>>y;
int ini = x - 'a';
int fin = y - 'a';
for(int i=0;i<26;i++)
{ if(ton[i] == ini)
ton[i] = fin;
else if(ton[i] == fin)
ton[i] = ini;
}
}
for(auto c:s)
{
cout<<(char)(ton[c-'a'] + 'a');
}
}
B.
using namespace std;
#define int long long
void solve()
{
int a,b;
cin>>a>>b;
if(gcd(a,b) != min(a,b))
cout<<-1<<endl;
else if(a==b)
{
cout<<1<<endl;
cout<<a<<endl;
}
else if(a!=b)
{
cout<<2<<endl;
cout<<min(a,b)<<' '<<max(a,b) - min(a,b)<<endl;
}
}
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
}
C.
using namespace std;
#define int long long
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a,b;
cin>>a>>b;
if(a > b)
swap(a,b);
if((a==0 && b == 2 ) )
{
cout<<"No"<<endl;
}
else if((a+b)%2 == 0)
{
cout<<"yEs"<<endl;
}
else
cout<<"no"<<endl;
}
D.
using namespace std;
#define int long long
/*
1. * 换成 ×
2. 第 i 块蛋糕，最好可以说随便吃。否则最开始会以为要按照顺序
*/
void solve()
{
int n;
cin>>n;
vector<int> a(n+1);
vector<int> b(n+1);
int ans = 0;
for(int i = 1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=n;i++)
ans += a[i]*b[i];
sort(a.begin()+1,a.end());
for(int i=1;i<=n;i++)
{
ans -= a[i]*(n-i);
}
cout<<ans<<endl;
}
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
}
E.
using namespace std;
#define int long long
const int N = 200+10;
char grid[N][N];
pair<int,int> ch[N][N];
map<pair<int,int> ,pair<int,int> > mp;
pair<int,int> st[N][N][64];
pair<int,int> dir [255];
int pow_2[61];
void pre()
{
pow_2[0] = 1;
for(int i=1;i<=60;i++)
pow_2[i] = pow_2[i-1] * 2;
}
signed main(){
pre();
dir['U'] = {-1,0};
dir['D'] = {1,0};
dir['L'] = {0,-1};
dir['R'] = {0,1};
int n,m,k,p;
cin>>n>>m>>k>>p;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>grid[i][j];
for(int i=1;i<=p;i++)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
ch[x1][y1] = {x2,y2};
}
string s;
cin>>s;
for(int i = 1;i<= n;i++)// st[i][j] == '.' or '#' 需要特判
for(int j = 1;j <= m;j ++)
if(grid[i][j] != '*')
st[i][j][0] = {i,j};
else
st[i][j][0] = ch[i][j];
//cout<<st[3][2][0].first<<" "<<st[3][2][0].second<<endl;
for(int k=1;k<=60;k++)
{
for(int i = 1;i<=n;i++)
for(int j=1;j<=m;j++)
{
auto [x,y] = st[i][j][k-1]; // 拿出那个下标
st[i][j][k] = st[x][y][k-1];
}
}
//cout<<st[3][2][1].first<<" "<<st[3][2][1].second<<endl;
int powe = 0; // 当前能量。
int x = 1,y = 1;
auto jud=[&](int x,int y)
{
if(x < 1 || x > n || y < 1 || y > m || grid[x][y] =='#')
return true;
else
return false ;
};
for(auto c:s)
{
//cout<<x<<' '<<y<<' '<<powe<<endl;
auto [dx,dy] = dir[c];
if(jud(x + dx, y + dy))
continue ;
powe += k;
x += dx, y += dy;
if(grid[x][y] == '.')
continue ;
for(int i=60;i>=0;i--)
{
if(pow_2[i] > powe)
continue ;
auto [nowx,nowy] = st[x][y][i];
// cout<<pow_2[i]<<' '<<powe<<endl;
if(grid[nowx][nowy] != '*')
continue ;
powe -= pow_2[i];
x = nowx,y = nowy;
}
if(powe)
{
auto [nowx,nowy] = st[x][y][0];
if(grid[nowx][nowy] == '#')
;
else{
powe -= 1;
x = nowx,y = nowy;
}
}
}
cout<<x<<' '<<y<<endl;
}
F.
using namespace std;
#define int long long
vector<int> hs[100];
int val[100];
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
cin>>val[i];
}
for(int i=0;i<m;i++)
{
int cnt;
cin>>cnt;
while(cnt--)
{
char x;
cin>>x;
hs[i].push_back(x - 'A');
assert(((x-'A') < n));
}
}
int ans = 0;
for(int i=0;i<(1<<m);i++)
{
if(__builtin_popcount(i) != k)
continue ;
vector<int> ton(100+1);
for(int j=0;j<m;j++){
if((i>>j)&1)
{
for(auto c:hs[j])
ton[c] ++;
}
}
int sum = 0;
for(int j=0;j<n;j++)
sum += (ton[j] >=2 )*ton[j]*val[j];
ans = max(ans,sum);
}
cout<<ans<<endl;
}
G.
using namespace std;
const int mod = 1e9 + 7;
int cal(string s) {
// 如果字符串以'0'开头，无法分割，直接返回0
if (s[0] == '0') return 0;
int n = s.size();
s= ' '+s;
// 预处理最长公共前缀（LCP）数组，lcp[i][j]表示从i和j开始的最长公共前缀长度
vector<vector<int>> lcp(n + 2, vector<int>(n + 2, 0));
for (int i = n ; i >= 1; --i) {
for (int j = n ; j >= 1; --j) {
if (s[i] == s[j]) {
lcp[i][j] = lcp[i + 1][j + 1] + 1;
} else {
lcp[i][j] = 0;
}
}
}
// cout<<lcp[1][3]<<endl;
// 辅助函数，判断s从l1开始的子串是否小于等于s从l2开始的子串（长度由r2 - l2决定）
auto lessEq = [&](int l1, int l2, int r2) {
int len = r2 - l2 + 1; // 第二个子串的长度
int len2 = l2 - l1 ;
if(len2 > len)
return false;
else if(len > len2)
return true;
int common = lcp[l1][l2];
// 如果公共前缀长度大于等于子串长度，则相等
if (common >= len) return true;
// 否则比较第一个不同的字符
return s[l1 + common] < s[l2 + common];
};
vector<int> sumd(n+1);
for(int i=1;i<=n;i++)
sumd[i] = (s[i] - '0');
for(int i=1;i<=n;i++)
(sumd[i] += sumd[i-1])%=3;
// dp数组，f[i][j]表示以i为起点、j为终点的分割方案数
vector<vector<int>> f(n+1, vector<int>(n+1, 0));
// 初始化：第一个字符到任意位置j的初始方案数为1
//f[i][j] 从i 到 j 的位置。
f[0][0] = 1;
for(int i=1;i<=n;i++)
{
if(sumd[i] == 0)
f[1][i] = 1;
}
//cout<<f[1][1]<<endl;
// for(int i=1;i<=n;i++)
// cout<<sumd[i]<<" \n"[i==n];
// cout<<lessEq(1,3,3)<<endl;
for (int i = 2; i <= n; ++i) {
// 当前字符为'0'，无法作为起点，跳过
if (s[i] == '0') continue;
int sum = 0; // 累计长度小于当前分割的情况数
int k = i - 1; // 前一个分割点的初始位置
for (int j = i; j <= n; ++j) {
// 初始情况下，累加所有长度小于当前分割长度的方案数
if((sumd[j] - sumd[i-1]) != 0 )
continue ;
// cout<<i<<endl;
f[i][j] = sum;
// cout<<i<<' '<<sum<<endl;
// 处理长度等于当前分割长度的情况
// cout<<k<<' '<<i<<" "<<j<<' '<<lessEq(k, i, j)<<endl;
while (k >= 1 && lessEq(k, i, j) ) {
// cout<<k<<' '<<i<<" "<<j<<endl;
// 前导非零且子串满足小于等于条件时，累加对应方案数
sum = (sum + f[k][i - 1]) % mod;
f[i][j] = sum;
// 将当前k对应的方案数加入sum，用于下一个j的长度较小情况
k--;
}
//cout<<i<<' '<<j<<" "<<k<<' '<<sum<<endl;
}
}
// 统计所有可能的起点i到终点的方案数
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + f[i][n]) % mod;
}
return ans;
}
signed main() {
int _;cin>>_;
assert(_<=5000);
int sz = 0;
while(_--) {
string w; cin >> w;
sz += w.size();
assert(sz <= 5000);
cout<< cal(w) << endl;
}
}
H.
using namespace std;
#define int long long
int ton[300];
int ton1[300];
int tr[1<<20][2];
int cnt = 1;
string str[1<<20]; // 存叶子结点的字符串
int base_32_to_10(string s)
{
return ton[s[0]]*(32768) + ton[s[1]]*(1024) + ton[s[2]] * 32 + ton[s[3]];
}
int cal_16_to_10(string s)
{
return ton1[s[0]]*65536 + ton1[s[1]]*(4096) +ton1[s[2]]*(256) + ton1[s[3]] * 16 + ton1[s[4]];
}
void add(int s,string now)
{
int ptr = 1;
for(int i=19;i>=0;i--)
{
int now = (s >> i) & 1;
//cout<<now;
if(!tr[ptr][now])
{
tr[ptr][now] = ++cnt;
}
ptr = tr[ptr][now];
}
//cout<<endl;
str[ptr] = now ;
}
void query(int s)
{
int ptr = 1;
for(int i=19;i>=0;i--)
{
int now = (s >> i) & 1;
//cout<<ptr<<' '<<now<<' '<<tr[ptr][now]<<' '<<tr[ptr][now^1]<<endl;
if(tr[ptr][now])
ptr = tr[ptr][now];
else
{
ptr = tr[ptr][now^1];
}
//cout<<ptr<<endl;
}
cout<<str[ptr]<<endl;
}
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for(int i=0;i<10;i++)
ton1['0'+i] = i;
for(int i=0;i<6;i++)
ton1['a'+i] = i + 10;
for(int i=0;i<26;i++)
ton['A'+i] =i;
for(int i=2;i<=7;i++)
ton['0'+i] = i +26 - 2;
int n;
cin>>n;
while(n--)
{
string s;
cin>>s;
if(s == "Join")
{
string a,b;
cin>>a>>b;
int val = cal_16_to_10(a);
// cout<<a<<' '<<val<<endl;
add(val,b);
}
else
{
string a;
cin>>a;
int len = a.size();
int val = base_32_to_10(a.substr(len - 4,4));
//cout<<a<<' '<<val<<endl;
query(val);
}
}
} ```
I.
```#include<bits/stdc++.h>
using namespace std;
#define int long long
string s[3];
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>s[0]>>s[1]>>s[2];
for(int i=0;i<4;i++)
{
if(s[0][i] == s[1][i])
cout<<s[0][i];
else
cout<<s[2][i];
}
}
J.
#define lc p<<1
#define rc p<<1|1
using ll = long long;
using namespace std;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(0, 1);
int a[50000+10];
template<typename T>
class Seg{
vector<T> tre;
vector<T> laz;
vector<T> sz;
public:
void pushdown(int p,int l,int r) {
if (laz[p]!=-1) {
tre[lc] = laz[p]*(sz[lc]&1);
tre[rc] = laz[p]*(sz[rc]&1);
laz[lc]=laz[p];
laz[rc]=laz[p];
laz[p]=-1;
}
}
void pushup(int p)
{
tre[p]=(tre[lc]^tre[rc]);
sz[p]=sz[lc]+sz[rc];
}
void build(int p,int l,int r){
if(l==r){
sz[p]=dis(gen);
if(sz[p])
tre[p] = a[l];
return;
}
int m=(l+r)>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(p);
}
Seg(int n):tre(4*n,0),laz(4*n,-1),sz(4*n,0){
;
}
void update(int p,int l,int r,int x,int y,T k){
if(x>r || y<l) return;
if(x<=l && r<=y){
laz[p]=k;
if(sz[p]&1) tre[p]=k;
else tre[p]=0;
return;
}
pushdown(p,l,r);
int m=(l+r)>>1;
update(lc,l,m,x,y,k);
update(rc,m+1,r,x,y,k);
pushup(p);
}
T query(int p,int l,int r,int x,int y){
if(x>r || y<l) return 0;
if(x<=l && r<=y) return tre[p];
pushdown(p,l,r);
int m=(l+r)>>1;
return (query(lc,l,m,x,y)^query(rc,m+1,r,x,y));
}
};
int p[110];
void insert(int x){
for(int i=63;i>=0;i--){
if(x&(1ll<<i)){
if(p[i]) x^=p[i];
else{
p[i]=x;
break;
}
}
}
}
int askmx(){
int x=0;
for(int i=63;i>=0;i--){
if((x^p[i])>x) x^=p[i];
}
return x;
}
void solve(){
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}
vector<Seg<int>> vt(60,Seg<int>(n+1));
for(int i=0;i<60;i++){
vt[i].build(1,1,n);
}
while(m--){
int op;
cin >> op;
if(op==1){
int l,r,x;
cin >> l >> r >> x;
for(int i=0;i<60;i++) vt[i].update(1,1,n,l,r,x);
}
else{
int l,r;
cin >> l >> r;
for(int i=0;i<=63;i++) p[i]=0;
for(int i=0;i<60;i++)
insert(vt[i].query(1,1,n,l,r));
cout << askmx() << "\n";
}
}
}
int main(){
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(0);
//cout.tie(0);
int _=1;
//cin >> _;
while(_--){
solve();
}
//system(pause);
return 0;
}
/*
5 3
1 2 3 4 5
1 1 3 1
2 1 3
2 2 4
5 1
1 1 1 4 5
2 2 4
1 1 1 4 5
1
5
*/
K.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
int n,q;
cin>>n>>q;
vector<int> a(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
vector<vector<int> > pre(n+1,vector<int> (100));
for(int i=1;i<=n;i++)
{
for(int j=0;j<=30;j++)
{
if((a[i] >> j) & 1)
pre[i][j] ++;
pre[i][j] += pre[i-1][j];
}
}
while(q--)
{
int id,k;
cin>>id>>k;
{
int l = 1;
int r = id;
int ans = 0;
while(l<=r)
{
int mid = l+r>>1;
int now = 0;
for(int i=0;i<=30;i++)
{
int num = pre[id][i] - pre[mid-1][i];
if(num == id - mid + 1)
now |= (1<<i);
}
if(now >= k - a[id])
{ ans = mid ;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
if(ans == 0)
{ cout<<"-1"<<endl;
continue ;
}
cout<<ans<<' ';
}
{
int l = id;
int r = n;
int ans = id;
while(l<=r)
{
int mid = l+r>>1;
int now = 0;
for(int i=0;i<=30;i++)
{
int num = pre[mid][i] - pre[id-1][i];
if(num)
now |= (1<<i);
}
if(now <= k + a[id])
{ ans = mid ;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout<<ans<<endl;
}
}
}
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
}
L.
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
string s;
cin>>s;
int k;
cin>>k;
vector<int> ton(30);
for(auto c:s)
{
ton[c-'a'] ++;
}
priority_queue<pair<int,int> > q;
for(int i=0;i<30;i++)
{
if(ton[i])
q.push({ton[i],i});
}
if(s.size() < k)
{
cout<<s<<endl;
return ;
}
queue<pair<int,int> > q1;
string ans ="";
int len = 0;
while(!q.empty())
{
auto [x,y] = q.top();
q.pop();
k -- ;
q1.push({x-1,y});
ans += 'a' + y;
if(k <= 0)
{
if(!q1.empty())
{
auto [x,y] = q1.front();
q1.pop();
if(x != 0)
q.push({x,y});
}
}
len ++;
}
if(len != s.size())
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
}
M.
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<array<int,4> > e[500000 + 10];
int dis[50000+10][4];
int vis[50000+10][4];
signed main (){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
int s,t;
cin>>s>>t;
for(int i=1;i<=m;i++)
{
int u,v,w,g,r;
cin>>u>>v>>w>>g>>r;
e[u].push_back({v,w,g,r});
}
priority_queue<array<int,3>,vector<array<int,3> >,greater<array<int,3> > > q;
//使用次数，时间，位置
q.push({0,0,s});
dis[s][0] = 0;
memset(dis,0x3f,sizeof dis );
while(!q.empty())
{
auto[t1,t2,pos] = q.top();
q.pop();
if(vis[pos][t1])
continue ;
vis[pos][t1] = 1;
for(auto [v,w,g,r]:e[pos])
{
int now = t2 %(g + r);
int res = g - now ;
if(res >= w )
{
if(dis[v][t1] > t2 + w)
{
dis[v][t1] = t2 + w;
q.push({t1,t2+w,v});
}
}
else
{ int nx = t2 - now + g + r + w;
if(dis[v][t1] > nx)
{
dis[v][t1] = nx;
q.push({t1,nx,v});
}
if(t1 + 1 < 3 && dis[v][t1 + 1] > t2 + w)
{
dis[v][t1 + 1] = t2 + w;
q.push({t1 + 1,t2 + w,v});
}
}
}
}
int ans = 0x3f3f3f3f3f3f3f3f;
for(int i=0;i<3;i++)
{
ans = min(ans,dis[t][i]);
}
if(ans == 0x3f3f3f3f3f3f3f3f)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
京公网安备 11010502036488号