2018湖南省赛选拔

2019-04-14 20:19发布

站内文章 / 模拟电子
16944 0 1714
class="markdown_views prism-github-gist"> 题目在CSUSTOJ：传送门 放一些有丶东西的题。

目录


模和最大

这里写图片描述 #include #define mme(a,b) memset((a),(b),sizeof((a))) #define fuck(x) cout<<"* "< #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.yuint main(){ while(~scanf("%d%d",&n,&p)){ for(int i=0;iscanf("%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;ifor(int i=0;iint 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;iif(i==n-1)printf("%d ", ans[i]); else printf("%d ", ans[i]); } } return 0; }

hash

这里写图片描述 #include #define mme(a,b) memset((a),(b),sizeof((a))) #define fuck(x) cout<<"* "< #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_mapint>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;iint 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;tscanf("%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;iint 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 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.dint n; int main(){ while(~scanf("%d", &n)){ priority_queueQ; for(int i=0;iscanf("%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(tmpcontinue; } nowt++; ans+=tmp; } printf("%lld ", ans); } return 0; }

搬东西-（这题还不会

这里写图片描述
不会，放标程吧 #include #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 #define per(i,a,b) for(int i=a-1;i>=b;--i) #define fuck(x) cout<<'['<<#x<<' '<<(x)<<']'< #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 #define lowbit(x) (x&(-(x))) #define mme(a,b) memset((a),(b),sizeof((a))) #define fuck(x) cout<<"* "< #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;iif(!noprime[i])pm[pcnt++]=i; for(int j=0;j1; 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]continue; LL st = a/pm[i]; if(st*pm[i]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 #define lowbit(x) (x&(-(x))) #define mme(a,b) memset((a),(b),sizeof((a))) #define fuck(x) cout<<"* "< #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_queueQ; Q.push(lp(1, 0, 1<1])); mme(dis,0x3f);dis[1][1<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<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;iscanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); } dij(); printf("%lld ", min(dis[1][6],dis[1][7])); } return 0; }

树分治？？？

这里写图片描述 #include #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<<"* "< #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;i2*k,greater<int>()); for(int i=0;ivoid 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;ireturn; } int num[11]={0,}; if(L<=mid){ query(L,R,l,mid,lson); for(int i=0;iif(R>mid){ query(L,R,mid+1,r,rson); for(int i=0;i2*k,greater<int>()); for(int i=0;iint 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;iprintf("%d%c", ans[i]," "[i==k-1]); } } } } return 0; }

py&hyh要妹子

这里写图片描述 #include #define lowbit(x) (x&(-(x))) #define mme(a,b) memset((a),(b),sizeof((a))) #define fuck(x) cout<<"* "< #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.tbool ok(int tim){ mme(ar, 0);mme(sum, 0); for(int i=0;iif(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(icontinue; 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;iscanf("%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 #define lowbit(x) (x&(-(x))) #define mme(a,b) memset((a),(b),sizeof((a))) #define fuck(x) cout<<"* "< #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]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;i1;++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的

热门文章