2018湖南省赛选拔

题目在CSUSTOJ：传送门

放一些有丶东西的题。

目录

• 目录

目录

####模和最大 

#include <bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))  
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const int N = 1e6 + 7;
int n, m, p;
struct lp{
  int a,yu,cha,id;
}cw[N];
int ar[N],ans[N],br[N];
bool cmp(lp &a,lp &b){
  return a.yu<b.yu;
}
int main(){
  while(~scanf("%d%d",&n,&p)){
    for(int i=0;i<n;++i){
      scanf("%d",&ar[i]);
      cw[i].a=ar[i];
      cw[i].yu=ar[i]%p;
      cw[i].cha=p-cw[i].yu;
      cw[i].id=i;
      br[i]=ar[i];
    }
    sort(cw,cw+n,cmp);
    for(int i=0;i<n;++i){
      ar[i]=cw[i].yu;
    }
    for(int i=0;i<n;++i){
      int k = lower_bound(ar,ar+n,cw[i].cha)-ar;
      //printf("%d %d %d

", cw[i].id,cw[i].yu,k);
      if(k==0||k==n){
        if(i==n-1){
          ans[cw[i].id]=(ar[n-2]+cw[i].a)%p;  
        }else{
          ans[cw[i].id]=(ar[n-1]+cw[i].a)%p;
        }
      }else{
        int a = (ar[n-1]+cw[i].a)%p;
        int b = (ar[n-2]+cw[i].a)%p;
        int c = (cw[k-1].yu+cw[i].a)%p;
        int d = (cw[k-2].yu+cw[i].a)%p;
        int e = (cw[k].yu+cw[i].a)%p;
        int sum=0;
        if(i==n-1){
          sum = b;
        }else{
          sum = b;
        }
        if(i==k-1){
          sum = max(sum,d);
        }else{
          sum = max(sum,c);
        }
        if(i!=k){
          sum = max(sum,e);
        }
        ans[cw[i].id]=sum;
      }
    }
    for(int i=0;i<n;++i){
      if(i==n-1)printf("%d
", ans[i]);
      else printf("%d ", ans[i]);
    }
  }
  return 0;
}

####hash 

#include <bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))  
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const int N = 2e6 + 7;
uLL base = 13131;
int n, m, p;
unordered_map<uLL,int>mp[N];
vector<int> son[N];
uLL col[N];
int flag;
void init(){
  for(int i=0;i<=m+10;++i)son[i].clear();
  for(int i=0;i<=m+10;++i)mp[i].clear();
}
void dfs(int u,int Fa,uLL cur,int dd){
  if(flag==0)return;
  int len = son[u].size();
  //printf("u=%d len=%d
", u,len);
  for(int i=0;i<len;++i){
    int v = son[u][i];
    if(v==Fa)continue;
    uLL tmp = cur*base+col[v];
    if(mp[dd+1][tmp]==0)flag=0;
    //printf("%llu %d %d %llu
",cur,v,col[v] ,tmp);
    if(flag==0)return;
    dfs(v,u,tmp,dd+1);
    if(flag==0)return;
  }
}
int main(){
  while(~scanf("%d%d",&n,&m)){
    init();
    for(int t=0;t<n;++t){
      scanf("%d",&p);
      uLL tmp=0,x;
      for(int i=1;i<=p;++i){
        scanf("%llu",&x);
        tmp = tmp*base+x;
        mp[i][tmp]=1;
        //printf("%llu
", tmp);
      }
    }
      //printf("**
");
      for(int i=1;i<=m;++i)scanf("%llu",&col[i]);
      for(int i=1;i<m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        son[u].push_back(v);
        son[v].push_back(u);
      }
      flag=1;
      dfs(1,0,col[1],1);
      if(flag==1)printf("YES
");
      else printf("NO
");
  }
  return 0;
}

####吃零食 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;

struct lp{
  int w,d,t;
  friend bool operator<(const lp &a, const lp &b){
    return a.d<b.d;
  }
}a, b;
int n;
int main(){
  while(~scanf("%d", &n)){
    priority_queue<lp>Q;
    for(int i=0;i<n;++i){
      scanf("%d%d",&a.w,&a.d);a.t=0;
      Q.push(a);
    }
    LL ans=0;
    int nowt=0;
    while(!Q.empty()){
      a = Q.top();Q.pop();
      LL tmp = a.w-(nowt-a.t)*a.d;
      if(tmp<=0){
        //nowt++;
        continue;
      }else if(tmp<a.d){
        b.w=b.d=tmp;
        b.t=nowt;
        Q.push(b);
        continue;
      }
      nowt++;
      ans+=tmp;
    }
    printf("%lld
", ans);
  }
  return 0;
}

####搬东西-（这题还不会  不会，放标程吧

#include <bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define x first
#define y second
#define add(x,y) ((x)+(y))%mod
#define sub(x,y) ((x)-(y)+mod)%mod
#define mul(x,y) ((x)%mod)*((y)%mod)%mod
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=a-1;i>=b;--i)
#define fuck(x) cout<<'['<<#x<<' '<<(x)<<']'<<endl;
#define FIN freopen("in.txt","r",stdin);
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<int, int> PII;

const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const int MX = 2e5 + 100;

int a[MX];
ll dp[MX][21];

int cal (int i, int j) {return abs (a[i] - a[j]);}

int main() {
    //FIN;
    int n, k; cin >> n >> k;
    rep (i, 1, 2 * n + k + 1) scanf ("%d", &a[i]);
    sort (a + 1, a + 2 * n + k + 1);
    rep (i, 0, 2 * n + k + 1) rep (j, 0, k + 1) dp[i][j] = INFLL;
    dp[0][0] = 0;
    rep (i, 1, 2 * n + k + 1)
        rep (j, 0, k + 1)rep (p, 0, k - j + 1) {
        dp[i][j + p] = min (dp[i][j + p], dp[i - j - 2][p] + cal (i, i - j - 1) );
        dp[i][j + p] = min (dp[i][j + p], dp[i - j][p]);
    }
    cout << dp[2 * n + k][k] << endl;
    return 0;
}

####简单数学题 

#include<bits/stdc++.h>
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a))) 
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;

int noprime[N],pm[N],pcnt=0;
void init(){
  noprime[0]=noprime[1]=1;
  for(int i=2;i<N;++i){
    if(!noprime[i])pm[pcnt++]=i;
    for(int j=0;j<pcnt&&i*pm[j]<N;++j){
      noprime[i*pm[j]]=1;
      if(i%pm[j]==0)break;
    }
  }
}
LL a, b, p;
int fa[N],vis[N];
int Fi(int x){
  return fa[x]==x?x:fa[x]=Fi(fa[x]);
}
void un(int a,int b){
  int pa = Fi(a), pb = Fi(b);
  if(pa==pb)return;
  fa[pb]=pa;
}
int main(){
  init();
  int tim, tc=0;
  scanf("%d", &tim);
  while(tim--){
    scanf("%lld%lld%lld", &a, &b, &p);
    for(LL i=0;i<=b-a;++i)fa[i]=i;
    mme(vis,0);
    for(int i=0; i < pcnt; ++i){
      if(pm[i]<p)continue;
      LL st = a/pm[i];
      if(st*pm[i]<a)st++;
      for(LL j = st+1; j*pm[i] <= b; ++j){
        LL t1 = j*pm[i], t2 = (j-1)*pm[i];
        un(t2-a,t1-a);
      }
    }
    int ans=0;
    for(int i=0;i<=b-a;++i){
      if(vis[Fi(i)]==0){
        vis[Fi(i)]=1;
        ans++;
      }
    }
    printf("Case #%d: %d
", ++tc, ans);
  }
  return 0;
}

####db要妹子 

#include<bits/stdc++.h>
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a))) 
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 2e5 + 7;
const int ME = 1e6+7;
const int mod = 1e9+7;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, tot;
struct lh{
  int v, nex;
  LL w;
}cw[ME];
struct lp{
  int v,sta;
  LL w;
  lp(){}
  lp(int a,LL b,int c){v=a;w=b;sta=c;}
  friend bool operator <(const lp &a,const lp &b){
    return a.w>b.w;
  }
}aa,bb;
int col[N];
LL dis[N][8];
int vis[N][8];
int head[N];

void dij(){
  priority_queue<lp>Q;
  Q.push(lp(1, 0, 1<<col[1]));
  mme(dis,0x3f);dis[1][1<<col[1]]=0;
  mme(vis,0);
  while(!Q.empty()){
    aa = Q.top();Q.pop();
    int u = aa.v, sta = aa.sta;
    if(vis[u][sta])continue;
    vis[u][sta] = 1;
    for(int i=head[u];~i;i=cw[i].nex){
      int v = cw[i].v, w = cw[i].w;
      int New = aa.sta | (1<<col[v]);
      if(dis[v][New]>dis[u][sta]+w){
        dis[v][New]=dis[u][sta]+w;
        Q.push(lp(v, dis[v][New], New));
      }
    }
  }
}
void init(){
  tot = -1;
  mme(head, -1);
}
void add_edge(int u,int v,int w){
  cw[++tot].v = v;cw[tot].w=w;cw[tot].nex=head[u];
  head[u]=tot;
  cw[++tot].v = u;cw[tot].w=w;cw[tot].nex=head[v];
  head[v]=tot;
}
int main(){
  while(~scanf("%d%d", &n, &m)) {
    for(int i = 1; i <= n; ++i){
      scanf("%d", &col[i]);
    }
    init();
    for(int i=0,u,v,w;i<m;++i){
      scanf("%d%d%d",&u,&v,&w);
      add_edge(u,v,w);
    }
    dij();
    printf("%lld
", min(dis[1][6],dis[1][7]));
  }
  return 0;
}

####树分治？？？ 

#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a))) 
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 5e5 + 7;
const int ME = 1e6+7;
const int mod = 1e9+7;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int ar[N], ans[5];
int sum[N<<2][5];
void push_up(int rt){
  int num[11]={0,};
  for(int i=0;i<k;++i){
    num[i]=sum[lson][i];
    num[i+k]=sum[rson][i];
  }
  sort(num,num+2*k,greater<int>());
  for(int i=0;i<k;++i){
    sum[rt][i]=num[i];
  }
}
void build(int l,int r,int rt){
  if(l==r){
    sum[rt][0]=ar[l];
    return;
  }
  int mid = (l+r)>>1;
  build(l,mid,lson);build(mid+1,r,rson);
  push_up(rt);
}
void update(int p,int c,int l,int r,int rt){
  int mid = (l+r)>>1;
  if(l==r){
    sum[rt][0]=c;
    return;
  }
  if(p<=mid)update(p,c,l,mid,lson);
  else update(p,c,mid+1,r,rson);
  push_up(rt);
}
void query(int L,int R,int l,int r,int rt){
  int mid = (l+r)>>1;
  if(L<=l&&r<=R){
    for(int i=0;i<k;++i){
      ans[i]=sum[rt][i];
    }
    return;
  }
  int num[11]={0,};
  if(L<=mid){
    query(L,R,l,mid,lson);
    for(int i=0;i<k;++i){
      num[i]=ans[i];
    }
  }
  if(R>mid){ 
    query(L,R,mid+1,r,rson);
    for(int i=0;i<k;++i){
      num[i+k]=ans[i];
    }
  }
  sort(num,num+2*k,greater<int>());
  for(int i=0;i<k;++i){
    ans[i]=num[i];
  }
}
int main(){
  while(~scanf("%d%d%d", &n, &m, &k)) {
    for(int i=1;i<=n;++i){
      scanf("%d", &ar[i]);
    }
    mme(sum, 0);
    build(1,n,1);
    //printf("**
");
    while(m--){
      int op,x,y;
      scanf("%d%d%d",&op,&x,&y);
      if(op==1){
        update(x,y,1,n,1);
      }else{
        query(x,y,1,n,1);
        for(int i=0;i<k;++i){
          printf("%d%c", ans[i]," 
"[i==k-1]);
        }
      }
    }
  }
  return 0;
}

####py&hyh要妹子 

#include<bits/stdc++.h>
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a))) 
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;


int n, m, k, q;
struct lp{
  int x,y,t;
}cw[N];
int sum[505][505], ar[505][505];

bool cmp(lp &a,lp &b){
  return a.t<b.t;
}
bool ok(int tim){
  mme(ar, 0);mme(sum, 0);
  for(int i=0;i<q;++i){
    if(cw[i].t>tim)break;
    ar[cw[i].x][cw[i].y]=1;
  }
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
      sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+ar[i][j];
      if(i<k||j<k)continue;
      int a = i - k +1, b = j - k + 1;
      if(sum[i][j]-sum[i][b-1]-sum[a-1][j]+sum[a-1][b-1]==k*k)return 1;
    }
  }
  return 0;
}
int main(){
  while(~scanf("%d%d%d%d", &n, &m, &k, &q)){
    int l = 0, r = 0, mid, ans=-1;
    for(int i=0;i<q;++i){
      scanf("%d%d%d", &cw[i].x,&cw[i].y,&cw[i].t);
      r=max(r,cw[i].t);
    }
    sort(cw,cw+q,cmp);
    while(r>=l){
      mid = (l+r)>>1;
      if(ok(mid)){
        ans=mid;
        r = mid-1;
      }else{
        l = mid+1;
      }
    }
    printf("%d
", ans);
  }
  return 0;
}

####神秘群岛 

#include<bits/stdc++.h>
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a))) 
#define fuck(x) cout<<"* "<<x<<"
"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
const int mod = 1e9+7;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, tot;
struct lp{
    int v,nex;
    LL w;
}cw[N*10];
int fa[N],head[N],dep[N],f[N][30];
LL size[N],dis[N], rdis[N];
void add(int x,int y,int w1,int w2){
  cw[++tot].v=y;cw[tot].w=w1*1LL;cw[tot].nex=head[x];
  head[x]=tot;
  cw[++tot].v=x;cw[tot].w=w2*1LL;cw[tot].nex=head[y];
  head[y]=tot;
}
void init(){
  tot=-1;
  memset(head,-1,sizeof(head));
  memset(fa,0,sizeof(fa));
  memset(f,0,sizeof(f));
  memset(dep,0,sizeof(dep));
  memset(size,0,sizeof(size));
  memset(dis,0,sizeof(dis));
  memset(rdis,0,sizeof(rdis));
}
void dfs(int  u,int Fa,int h){
    dep[u]=h;f[u][0]=Fa;fa[u]=Fa;
    for(int i=1;i<20;++i){
        int cf=f[u][i-1];
        f[u][i]=f[cf][i-1];
    }
    for(int i=head[u];~i;i=cw[i].nex){
        int v=cw[i].v;
        LL w1=cw[i].w,w2=cw[i^1].w;
        if(v==Fa)continue;
        dis[v]=dis[u]+w1;
        rdis[v]=rdis[u]+w2;
        dfs(v,u,h+1);
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])x^=y^=x^=y;
    for(int i=19;i>=0;--i){
        if(dep[f[x][i]]>=dep[y]){
            x=f[x][i];
        }
    }
    if(x==y)return x;
    for(int i=19;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];y=f[y][i];
        }
    }
    return f[x][0];
}
int main(){
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    init();
    LL Sum=0;
    for(int i=0;i<n-1;++i){
      int u,v;
      LL w1,w2;
      scanf("%d%d%lld%lld",&u,&v,&w1,&w2);
      add(u,v,w1,w2);
      Sum+=w1+w2;
    }
    dfs(1,0,0);
    scanf("%d",&m);
    while(m--){
      int a,b;scanf("%d%d",&a,&b);
      int ff=LCA(a,b);
      swap(a,b);
      LL ans1 = rdis[a]-rdis[ff];
      LL ans2 = dis[b]-dis[ff];
      printf("%lld
", Sum-ans1-ans2);
    }
  }
  return 0;
}

挺sb的