2019徐州网络赛题解
比赛地址
[A]Who is better?
题意
给定一个同余方程组,求其最小整数解.然后根据这个解进行一个博弈游戏.设解为n,则有n个石子.双方轮流取石子,第一次至少取1个石子,但不能拿完.设第i次取了x个,则i+1次只能取1~2x个.谁取走最后一个石子谁赢.求先手必胜还是必负.
题解
先拿广义中国剩余定理求解,得到n.然后暴力打表找规律,发现当n是斐波那契数的时候,后手必胜.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 15
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int i,k;
int a[5];
LL n,low,high,mid,ss;
LL p[N],r[N],f[10010];
inline LL Abs(LL x){return (x<0)?-x:x;}
inline void Swap(LL &a,LL &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline LL Gcd(LL a,LL b){return (!b)?a:Gcd(b,a%b);}
inline void Ex_gcd(LL a,LL b,LL &x,LL &y){
LL p=0,q=0;
if (b==0) {
x=1; y=0; return;
} else {
Ex_gcd(b,a%b,p,q);
x=q; y=p-a/b*q;
}
}
inline LL Solve(){
int i=0;
LL a=0,b=0,c=0,gcd=0,k1=0,k2=0;
for (i=1;i<k;i++){
a=p[i]; b=p[i+1]; c=r[i+1]-r[i];
gcd=Gcd(a,b);
if (c%gcd) return -1;
a/=gcd; b/=gcd; c/=gcd;
Ex_gcd(a,b,k1,k2);
k1=((k1*c)%b+b)%b;
p[i+1]=p[i]/gcd*p[i+1];
r[i+1]=(k1*p[i]%p[i+1]+r[i])%p[i+1];
}
return r[k];
}
int main(){
scanf("%d",&k);
for (i=1;i<=k;i++)
scanf("%lld%lld",&p[i],&r[i]);
n=Solve();
if (n==-1){
cout<<"Tankernb!";
return 0;
}
f[1]=1; f[2]=2;
for (i=3;i<=72;i++)
f[i]=f[i-1]+f[i-2];
for (i=1;i<=72;i++){
if (n==f[i]){
cout<<"Lbnb!"<<endl;
return 0;
}
}
cout<<"Zgxnb!"<<endl;
return 0;
}
比赛的时候读错题了啊啊啊,表都打出来一个了,虽然是错的...差点就A了
[B]So easy
题意
给出长度为n的一个列表,有m个操作.第一种操作是把列表的x位置置为不可用,第二种操作是询问x位置后面第一个可用的位置是什么(包括自己).对于所有的询问操作,输出答案.
题解
考虑使用并查集维护联通关系.每次遇到置为不可用的操作,就把x位置前后的两个元素中的不可用元素和x合并,同时记录集合的大小,也就是连续的不可用区间的长度.对于所有的询问操作,先检查后面相邻的元素是否可用,如果不可用,就可以根据集合大小找到第一个可用元素.
因为数据规模较大所以需要拿map离散一下.(第一次用unordered_map,听说插入和询问都是O(1)的,新技能get,只是在判断是否为空的时候需要借助特殊的函数)
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<unordered_map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,x,y,fa,z;
unordered_map <int,int> f,v,size;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
namespace IO{
char buf[1<<15],*fs,*ft;
inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int gint(){
int x=0,ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=gc();
return x;
}
}
using namespace IO;
inline int Find(int x){return (f[x]==x)?x:f[x]=Find(f[x]);}
int main(){
n=gint(); m=gint();
for (i=1;i<=m;i++){
x=gint(); y=gint();
if (x==2&&y==n){
if (v.count(y)) puts("-1");
else printf("%d\n",y);
continue;
}
if (x==1){
if (v.count(y)) continue;
v[y]=1; z=f[y]=y; size[y]=1;
if (y+1<=n&&v.count(y+1)){
fa=Find(f[y+1]);
f[fa]=z; size[z]+=size[fa];
}
if (y-1&&v.count(y-1)){
fa=Find(f[y-1]);
f[z]=fa; size[fa]+=size[z];
}
continue;
}
if (!v.count(y)) {printf("%d\n",y); continue;}
if (!v.count(y+1)) {printf("%d\n",y+1); continue;}
else {
fa=Find(y+1);
fa=fa+size[fa];
if (fa<=n) printf("%d\n",fa);
else puts("-1");
}
}
return 0;
}
[C]Buy Watermelon
题意
给定一个数n,判断能不能把n分成两部分,使得每一部分都是2的倍数.
题解
签到题
代码
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
if(n%2==0&&n!=2)
puts("YES");
else
puts("NO");
return 0;
}
[D]Carneginon
题意
给定一个串,然后有m次询问,每次会再次给定一个串,判断短一点的那个串是不是长串的子串.如果长度相同,就判断是不是相等.
题解
考虑到题目中有
m(|S|+|T|)\leq 1e7
所以直接套KMP即可.长度相等就暴力判断.
代码
#include <cstdio>
#include <cstring>
constexpr int MQ(2e3+6);
constexpr int ML(2e5+6);
constexpr int MN(5e6+5);
constexpr int MA(26);
char len_cmp[MQ];
bool has[MQ];
bool belong[MQ];
bool eq[MQ];
struct KMPer
{
char *str;
int len;
int next[ML];
int get_next(char *s, int l)
{
len = l, str = s;
int i = 0, j = next[0] = -1;
while (i < len)
{
if (j==-1 || s[i]==s[j])
next[++i] = ++j;
else
j = next[j];
}
return len;
}
void get_next_t(char *p, int l)
{
str = p;
len = l;
int t1 = 0, t2;
next[0] = t2 = -1;
while (t1 < l)
if (t2==-1 || p[t1]==p[t2])
next[++t1] = ++t2;
else t2 = next[t2];
}
bool kmp(char *p, int l)
{
int t1=0, t2=0;
while (t1 < l)
{
if (t2==-1 || p[t1]==str[t2])
t1++, t2++;
else t2 = next[t2];
if (t2 == len)
return true;
}
return false;
}
} ker;
char t[ML], s[ML];
int main()
{
int n;
scanf("%s %d", t, &n);
int len_t = strlen(t);
for (int i=1; i<=n; ++i)
{
scanf("%s", s);
int len_s = strlen(s);
if (len_s > len_t)
{
len_cmp[i] = 1;
ker.get_next(t, len_t);
belong[i] = ker.kmp(s, len_s);
}
else if (len_s < len_t)
{
len_cmp[i] = -1;
ker.get_next(s, len_s);
has[i] = ker.kmp(t, len_t);
}
else
{
len_cmp[i] = 0;
eq[i] = !strcmp(s, t);
}
}
for (int i=1; i<=n; ++i)
{
if (len_cmp[i] == 1) // len_s > len_t
{
puts(belong[i] ? "my teacher!" : "senior!");
}
else if (len_cmp[i] == -1)
{
puts(has[i] ? "my child!" : "oh, child!");
}
else
{
puts(eq[i] ? "jntm!" : "friend!");
}
}
return 0;
}
[E]XKC's basketball team
题意
CXK有一个篮球队,编号1~n.每个人有一个能力值,对于第i个人,设其能力值为w.如果存在一个编号比他大而且能力值不小于w+m的人,他就会angry.求对于每个人,让他angry的人中距离他最远的人有多远.距离的定义是两人之间的其他人的数量.如果没有输出-1.
题解
按照能力值排序.以排序后各个元素的原始位置作为权值,用ZKW线段树维护区间最大值.然后对第i个人二分出数列中不小于w+m的最小序号.然后在ZKW线段树上查询.如果编号小于i则输出-1,否则直接输出答案.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 500010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i;
int b[N],c[N],Ans[N];
int f[N][22];
struct Data{
int x,y;
bool operator <(const Data &o) const{
return y<o.y;
}
bool operator >(const Data &o) const{
return y>o.y;
}
}a[N];
inline bool cmp(const Data &c,const Data &b){return c.x<b.x;}
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
template <typename sint, typename xint = int>
class ZKW
{
private:
sint t[N << 2];
xint n, _offset; // 必须要有offset
#define _getl(l) l-_offset
#define _getr(r) r+1-_offset
#define li i<<1
#define ri i<<1|1
#define pu(i) \
({ \
t[i] = t[li]>t[ri]?t[li]:t[ri]; \
})
public:
void build(const sint *arr, const xint l, const xint r) // 注意arr也是sint*类型！否则下面memcpy就不匹配了
{
_offset = l; // [l, r] -> [0, n), 则_getl(l)==l-_offset==0, 则_offset==l; _getl(r)==r+1-_offset==n, 也能推出_offset==l。
n = r-l+1;
memcpy(t+n, arr+l, sizeof(sint) * n);
for (int i=n-1; i; --i)
pu(i);
}
void add(xint p, const sint v)
{
for (t[p=_getl(p)+n]+=v; p>1; p>>=1)
t[p>>1] = t[p] + t[p^1];
}
sint max(xint l, xint r)
{
sint maxv = (Data){-1,-1}, tpp;
for (l=_getl(l)+n, r=_getr(r)+n; l<r; l>>=1, r>>=1)
{
if (l&1)
{
tpp = t[l++];
if (tpp > maxv)
maxv = tpp;
}
if (r&1)
{
tpp = t[--r];
if (tpp > maxv)
maxv = tpp;
}
}
return maxv;
}
};
ZKW <Data> T;
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Ready(){
int i=0;
T.build(a,1,n);
for (i=1;i<=n;i++) c[i]=a[i].x;
}
inline bool Check(int x,int y){
return a[x].x>=y;
}
inline int Query(int x,int y){
return T.max(x,y).y;
}
inline int Find(int x){
return lower_bound(c+1, c+n+1, x) - c;
}
inline void Work(){
int i=0,low=1,high=n,mid=0,ans=0;
for (i=1;i<=n;i++){
ans=Find(b[i]+m);
if (ans>n){
Ans[i]=-1; continue;
}
ans=Query(ans,n);
if (ans<i) Ans[i]=-1; else Ans[i]=ans-i-1;
}
for (i=1;i<n;i++) printf("%d ",Ans[i]);
printf("%d",Ans[n]);
}
int main(){
n=read(); m=read();
for (i=1;i<=n;i++){
a[i].x=read(); a[i].y=i;
b[i]=a[i].x;
}
sort(a+1,a+1+n,cmp);
Ready(); Work();
return 0;
}
[G]Colorful String
题意
对于每一个回文串,定义其价值是所含有的不同字母的数量.然后给定一个字符串,求其所有回文子串的价值总和.
题解
先跑一遍Manachar.然后对于每一个位置,预处理出26个字母的第一次出现的位置.对于每一个回文中心,先计算出回文半径,然后枚举26个字母,检查是否落在了半径之内.如果是,则算一下对答案的贡献.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 300010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,cnt;
char c[N],C[N*2];
int p[N*2],h[N*2][26];
LL Ans;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Manachar(){
int i=0,mx=0,id=0;
for (i=2;i<cnt;i++){
if (i<mx) p[i]=Min(p[2*id-i],mx-i); else p[i]=1;
while (C[i+p[i]]==C[i-p[i]]) p[i]++;
if (i+p[i]>mx) mx=i+p[i],id=i;
}
}
inline void Ready(){
int i=0,j=0,p=-1;
for (i=0;i<n;i++){
C[++cnt]='#'; C[++cnt]=c[i];
}
C[++cnt]='%';
for (i=0;i<=25;i++){
p=-1;
for (j=cnt;j;j--){
if (C[j]-'a'==i) p=j;
h[j][i]=p;
}
}
Manachar();
}
inline void Work(){
int i=0,j=0,r=0,x=0;
for (i=1;i<cnt;i++){
r=p[i];
if (C[i]!='#') r=(r+1)/2;
else r=r/2;
if (!r) continue;
// cout<<C[i]<<" "<<r<<endl;
for (j=0;j<=25;j++){
x=h[i][j];
if (x==-1) continue;
if (C[i]!='#') {
x=(x-i)/2+1;
if (x<=r){
Ans+=(LL)(r-x+1);
// cout<<C[i]<<" "<<r<<" "<<j<<" "<<x<<endl;
}
} else {
x=(x-i+1)/2;
if (x<=r) {
// cout<<C[i]<<" "<<r<<" "<<j<<" "<<x<<endl;
Ans+=(LL)(r-x+1);
}
}
}
}
// for (i=1;i<=cnt;i++) cout<<i<<" "<<p[i]<<endl;
cout<<Ans<<endl;
}
int main(){
scanf("%s",&c);
n=strlen(c);
Ready(); Work();
//cout<<h[4][1]<<endl;
return 0;
}
[J]
题意
给出一棵树和一段伪代码.求程序按照伪代码运行时求出正确树高的概率.
伪代码的内容为:把Dfs时选择子节点的过程改为随机选取.
题解
树形dp.
设dp[x]表示选择x节点后得到正确树高的概率.然后跑树形dp.注意要先求出进行一次选择后,求出正确树高的概率.然后反向算出在一定次数的选择后不能求出树高的概率,再拿1减去上面的结果即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 1000010
#define MOD 1000000007ll
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,lsum=1,dep,x,y;
int d[N],v[N],head[N];
LL inv[N],dp[N];
struct Flow{
int t,next;
}e[N*4];
inline int Max(int a,int b){return (a>b)?a:b;}
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
inline void Ready(){
LL i=0;
inv[1]=1;
for (i=2;i<=1000000;i++)
inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
}
inline LL Mi(LL x,LL y){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
inline void Make(int x){
int i=0;
dep=Max(dep,d[x]);
for (i=head[x];i;i=e[i].next)
if (!d[e[i].t]){
d[e[i].t]=d[x]+1; Make(e[i].t);
}
}
inline void Dfs(int x){
int i=0;
LL tot=0,p=0,s=0,sum=0;
dp[x]=0;
if (d[x]==dep){dp[x]=v[x]=1; return;}
for (i=head[x];i;i=e[i].next){
if (d[e[i].t]<d[x]) continue;
tot++; Dfs(e[i].t);
if (v[e[i].t]) v[x]=1,sum+=dp[e[i].t];
}
if (!v[x]) {dp[x]=0; return;}
sum=(sum*inv[tot])%MOD;
s=(1-sum+MOD)%MOD;
s=Mi(s,tot);
dp[x]=(1-s+MOD)%MOD;
}
int main(){
scanf("%d",&n);
Ready();
for (i=1;i<n;i++){
scanf("%d%d",&x,&y);
Add(x,y); Add(y,x);
}
d[1]=1; Make(1); Dfs(1);
cout<<dp[1]<<endl;
return 0;
}
[K]Center
题意
给定n个点,求出最少需要补上几个点(位置任意),可以使得所有的点构成一个中心对称图形.
题解
考虑到要使补充的点的数量最少,就要尽可能在原来的点中找出尽可能多的对称点对.所以暴力枚举所有的二元点对,计算其对称中心,扔到map里离散化一下.然后统计出每个对称中心最多能够利用多少个点.答案就是点数减去最多利用的点数.
对于重点的情况要特殊处理.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 1010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,cnt,Ans;
struct Data{
int x,y,z;
bool operator <(const Data &b) const{
return (x==b.x)?y<b.y:x<b.x;
}
}a[N],b[N];
map <Data,int> M;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline bool cmp(const Data &a,const Data &b){return (a.x==b.x)?a.y<b.y:a.x<b.x;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Work(){
int i=0,j=0;
Data p;
for (i=1;i<=cnt;i++)
for (j=i+1;j<=cnt;j++){
p.x=(b[i].x+b[j].x)/2;
p.y=(b[i].y+b[j].y)/2;
M[p]+=b[i].z+b[j].z;
if (M[p]>Ans) Ans=M[p];
}
for (i=1;i<=cnt;i++){
p.x=b[i].x; p.y=b[i].y;
M[p]+=b[i].z;
if (M[p]>Ans) Ans=M[p];
}
cout<<n-Ans<<endl;
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].x*=2; a[i].y*=2;
}
sort(a+1,a+1+n);
a[0].x=-5689; a[0].y=-599;
for (i=1;i<=n;i++){
if (a[i].x==a[i-1].x&&a[i].y==a[i-1].y){
b[cnt].z++; continue;
}
cnt++;
b[cnt]=a[i]; b[cnt].z++;
}
if (cnt==1){
cout<<"0"<<endl;
return 0;
}
Work();
return 0;
}
[M]Longest subsequence
题意
给出两个字符串T和S.求T中的最长子序列L,使得L的字典序严格大于S.如果无解,输出-1.
题解
设S开头的字母为c.首先考虑L点的开头字母p.如果p的字典序大于c,则可以取位置最靠前的p,然后一直到结尾构成的子序列即为L.当p的字典序等于c时,考虑一位一位枚举L的字母,然后在T中进行跳转选取子序列.这时需要预处理对于每一个位置,26个字母的第一次出现的位置.每次选择字母时,均贪心选择最靠前的那个字母.正确性显然.
设接下来该匹配到了S的第x位,原串T选择到了第y位.此时无非有两种选择:字典序大于S或者等于S.当无法选择字母使得字典序不小于S时,该情况无解.如果选择大于x的字典序,则依次枚举大于S当前位置的字母,求y位置后最靠前的这些字母,统计答案,然后结束这一过程.或者选择字典序相等的字母,利用预处理的结果跳转y.最后统计答案即可.
具体细节见代码.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 1000010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,j,x,Ans,y;
int h[50],w[50],f[N][26];
char c[N],s[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",c+1);
scanf("%s",s+1);
for (i=0;i<=25;i++) w[i]=-1;
for (i=n;i;i--){
for (j=0;j<=25;j++) f[i][j]=w[j];
x=c[i]-'a'; h[x]=i;
w[c[i]-'a']=i;
}
Ans=-1;
for (i=s[1]-'a'+1;i<=25;i++)
if (h[i]) Ans=Max(Ans,n-h[i]+1);
// cout<<Ans<<endl;
if (Ans==-1&&h[s[1]-'a']==0){
cout<<"-1"<<endl;
return 0;
}
x=1; y=h[s[1]-'a'];
while (x<m&&y>0){
x++;
for (i=s[x]-'a'+1;i<=25;i++)
if (f[y][i]>0)
Ans=Max(Ans,x-1+n-f[y][i]+1);
y=f[y][s[x]-'a'];
}
//cout<<y<<endl;
if (y==n) {
printf("%d\n",Ans);
return 0;
}
if (y>0) Ans=Max(m+n-y,Ans);
cout<<Ans<<endl;
return 0;
}
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2019徐州网络赛题解
本文地址: 2019徐州网络赛题解
