USST新生训练赛3KLMN

本文主要是介绍USST新生训练赛3KLMN，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解

• 前言
• 题解部分
• • K Pashmak and Parmida's problem(1800)
  • • 题目大意
    • 题解
    • 参考代码
  • L Pashmak and Graph(1900)
  • • 题目大意
    • 题解
    • 参考代码
  • M Lucky Chains(1600)
  • • 题目大意
    • 题解
    • 参考代码
  • N Manipulating History(1600)
  • • 题目大意
    • 题解
    • 参考代码

前言

KLMN是数据结构（线段树/树状数组）+dp+数论+结论唐题

题解部分

K Pashmak and Parmida’s problem(1800)

原题链接：https://codeforces.com/problemset/problem/459/D

题目大意

给定长度为$n$（$1\le n\le 10^6$）的序列$a$（$1\le a_i\le 10^9$），定义$f(i,j,x)$为$a_i\dots a_j$中$x$的出现次数，求有多少对$f(1,i,a_i)$和$f(j,n,a_j)$满足$f(1,i,a_i)>f(j,n,a_j)$且$i<j$

题解

根据题意可以看出，这个题的感觉很像逆序对界·逆序对，回忆一下逆序对是怎么做的，归并或者是树状数组，但是u1s1，归并不是很好做，我们选择BIT也就是树状数组或者你要是会权值线段树也行，树状数组的具体细节可以去看oiwiki的树状数组，那么最终这道题该怎么完成呢
我们注意到如果我们先求逆序对，那么这步的复杂度就是$O(nlogn)$，结合这道题的数据范围我们就需要$O(1)$求出$f(i,j,x)$，但是显然这不是很能做得到，所以我们可以反过来想，我们先预处理出所有的$f(i,j,x)$，然后往树状数组里倒序插入处理好的所有数据，再依次求就行
到这里这道题仍然不能满分，我们注意到序列元素范围很大，所以要进行离散化，离散化的具体细节也可以去看oiwiki的离散化
最终时间复杂度$O(nlogn)$
建议大家这道题不要借鉴我的写法，因为没有人会这么写这道题

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
inline int read(){int x(0),w(1); char c = getchar();while(c^'-' && (c<'0' || c>'9')) c = getchar();if(c=='-') w = -1, c = getchar();while(c>='0' && c<='9') x = (x<<3)+(x<<1)+c-'0', c = getchar(); return x*w;
}
struct node{ int idx,val,rnk; }a[N];
int n,ans,v[N],p,A[N],B[N];
inline bool cmp1(const node& A, const node& B){return A.val < B.val;}
inline bool cmp2(const node& A, const node& B){return A.idx < B.idx;}
inline void modify(int i, int k){for(; i <= n; i += i&(-i)){v[i] += k;}
}
inline int query(int i){int res = 0;for(; i > 0; i -= i&(-i)){res += v[i];}return res;
}
signed main(){n = read();for(int i = 1; i <= n; ++i){a[i].val = read();a[i].idx = i;}sort(a+1,a+n+1,cmp1);a[1].rnk = p = 1;for(int i = 2; i <= n; ++i){a[i].rnk = (a[i].val==a[i-1].val) ? p : ++p;}sort(a+1,a+n+1,cmp2);for(int i = 1; i <= n; ++i){modify(a[i].rnk,1);A[i] = query(a[i].rnk)-query(a[i].rnk-1);}memset(v,0,sizeof(v));for(int i = n; i >= 1; --i){modify(a[i].rnk,1);B[i] = query(a[i].rnk)-query(a[i].rnk-1);}memset(v,0,sizeof(v));for(int i = 1; i <= n; ++i){modify(B[i],1);}for(int i = 1; i < n; ++i){modify(B[i],-1);ans += query(A[i]-1);}printf("%lld",ans);return 0;
}

L Pashmak and Graph(1900)

原题链接：https://codeforces.com/problemset/problem/459/E

题目大意

给定$n$个点$m$条带权边的有向图。 现在请你找一条路径，起点和终点自取，在保证路径上的边权严格递增（即 下一条边的$v$严格大于上一条的$v$）的情况下包含最多的边。 每条边只用一次。请输出路径最多能包含多少条边。

第一行输入$2$个数字$n$,$m$, 表示$n$个点$m$条有向边。 第$2$到$m+1$行每行$3$个数$s$,$t$和$v$，表示边的起点、终点、边权。

题解

这个问题其实可以直接转化为一个在图上跑的最长上升子序列，对边权进行升序排序，记录到每个点的最长路径最后取最大值，注意到边权需要严格递增，所以需要暂存旧值，对边权相等的点分别计算dp值，然后再赋新值

参考代码

#include<bits/stdc++.h>
#define N 300005
#define ll long long
#define ms(ar,x) memset(ar,x,sizeof(ar))
#define fn(i,st,ed) for(int i=st;i<=ed;i++)
#define fd(i,st,ed) for(int i=st;i>=ed;i--)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;
}
struct edge{int x,y,z;}e[N<<1];
bool cmp(edge x,edge y){return x.z<y.z;}
int dp[2][N];
int main(){//freopen("graph.in","r",stdin);//freopen("graph.out","w",stdout);int n=read(),m=read(),ans=0;fn(i,1,m)e[i]=(edge){read(),read(),read()};sort(e+1,e+1+m,cmp);fn(i,1,m){int j=i;while(e[i].z==e[j].z&&j<=m)j++;fn(k,i,j-1)dp[0][e[k].y]=max(dp[0][e[k].y],dp[1][e[k].x]+1);fn(k,i,j-1)dp[1][e[k].y]=dp[0][e[k].y];i=j-1;}fn(i,1,n)ans=max(ans,dp[1][i]);printf("%d\n",ans);return 0;
}
/*
6 7
1 2 1
3 2 5
2 4 2
2 5 2
2 6 9
5 4 3
4 3 4
*/

M Lucky Chains(1600)

原题链接：https://codeforces.com/problemset/problem/1766/D

题目大意

给定两正整数$x$，$y$，满足所有$(x,y)$到$(x+k,y+k)$均互质，并且从$(x+k+1,y+k+1)$开始不互质，求$k$

题解

由欧几里得定理可知，$gcd(x,y)=gcd(x-y,y)$
因此，对于题目中的$gcd(x+k+1,y+k+1)=gcd(x-y,y+k+1)$，我们需要求出一个数字$\alpha$，这个数字需要是$x-y$的质因子的倍数并且大于$x+k+1$，求出$\alpha$的最小值即是答案，这样这个数字就是令$gcd(x+k+1,y+k+1)>1$的最小值

参考代码

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 20000005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
int p[MAXN],prime[MAXN],tot;
void init(){fn(i,2,MAXN-1){if(!p[i])p[i]=i,prime[++tot]=i;for(int j=1;j<=tot&&prime[j]*i<MAXN;j++){p[prime[j]*i]=prime[j];if(p[i]==prime[j])break;}}
}
void solve(){int a,b;cin>>a>>b;int c=b-a,ans=INF;while(c>1){int x=p[c];while(p[c]==x)c/=x;int nxt=(a/x)*x;if(nxt<a)nxt+=x;ans=min(ans,nxt);}if(ans==INF)ans=a-1;cout<<ans-a<<endl;
}
signed main(){init();ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){solve();}return 0;
}

N Manipulating History(1600)

原题链接：https://codeforces.com/problemset/problem/1688/C

题目大意

有一个未知的长度为$1$的字符串，和一组长度为$n$的改变操作。每次操作将字符串中任意一个出现的子串$t_{2i-1}$替换成$t_{2i}$，最后得到一个新的字符串。将操作序列的$2n$个字符串打乱顺序，求出唯一的原字符串，保证有解。

题解

唐题一道
注意到起始长度为$1$，该字符最终状态只有两种情况，不变或者被替换，被替换则一定会在第一轮被替换所以只会出现一次，如果不变那前面会出现偶数次最后出现一次也是奇数次，然后证为什么其他字符一定会出现偶数次，其实就是因为第一个字符串一定不会出现后面的，所以后面的会出现$2i-1$次，然后最后出现一次，所以必定是偶数次，所以就找唯一出现奇数次的字符就行

参考代码

#include<bits/stdc++.h>
#define INF 2147483647LL
#define int long long
#define MAXN 300005
#define mod 1000000007
#define PI 3.14
#define eps 1e-10
#define pa pair<int,int>
#define ms(a,x) memset(a,x,sizeof(a))
#define mc(ar1,ar2) memcpy(ar1,ar2,sizeof(ar2))
#define mkp(a,b) make_pair(a,b)
#define ls (p<<1)
#define rs (p<<1|1)
#define fn(i,st,ed) for(int i=st;i<=ed;++i)
#define fd(i,st,ed) for(int i=st;i>=ed;--i)
#define fg(i,x,head,e) for(int i=head[x];~i;i=e[i].nxt)
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
int vis[26];
void solve(){int n;cin>>n;ms(vis,0);fn(i,0,2*n){string s;cin>>s;fn(j,0,s.size()-1)vis[s[j]-'a']++;}fn(i,0,25)if(vis[i]&1){cout<<(char)(i+'a')<<endl;return;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){solve();}return 0;
}

这篇关于USST新生训练赛3KLMN的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---