首页 > 代码库 > 2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）(5/10)
2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）(5/10)
1001: 传递要求 a->b->c && a->c
我的做法就是利用bitset预处理出x点可达点集，与可达到x点的点集
那么如何检验这个图是否传递；枚举完b和，枚举可达b点集中的点x，那么点x可达点集要包含c点集，这个利用bieset可以快速判断
整个做法就是(n^2)
#include<cstdio>#include<cstring>#include<iostream>#include<sstream>#include<algorithm>#include<vector>#include<bitset>#include<set>#include<queue>#include<stack>#include<map>#include<cstdlib>#include<cmath>#define PI 2*asin(1.0)#define LL long long#define pb push_back#define pa pair<int,int>#define clr(a,b) memset(a,b,sizeof(a))#define lson lr<<1,l,mid#define rson lr<<1|1,mid+1,r#define bug(x) printf("%d++++++++++++++++++++%d\n",x,x)#define key_value ch[ch[root][1]][0]const int MOD = 1000000007;const int N = 2016+15;const int maxn = 200+ 14;const int mm=100010;const int letter = 130;const int INF = 1e9;const double pi=acos(-1.0);const double eps=1e-8;using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int T,n;char s[N][N];bitset<N>vs[2][N],tt;int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++) vs[0][i].reset(),vs[1][i].reset(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(s[i][j]==‘P‘){ vs[1][i][j]=vs[0][j][i]=1; } } } int flag=1; for(int x=1;x<=n;x++){ for(int i=1;i<=n;i++){ if(vs[0][x][i]){ tt=vs[1][i]&vs[1][x]; if(tt!=vs[1][x]){flag=0;break;} } } if(!flag) break; } if(!flag){ puts("N"); continue; } for(int i=1;i<=n;i++) vs[0][i].reset(),vs[1][i].reset(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(s[i][j]==‘Q‘){ vs[1][i][j]=vs[0][j][i]=1; } } } flag=1; for(int x=1;x<=n;x++){ for(int i=1;i<=n;i++){ if(vs[0][x][i]){ tt=vs[1][i]&vs[1][x]; if(tt!=vs[1][x]){flag=0;break;} } } if(!flag) break; } if(flag) puts("T"); else puts("N"); } return 0;}
1003：对于给定以x为根的游戏，我们把看看作是多条链的组合游戏（组合博弈）
那么一条链怎么赢？
我们以低位为接近根的边权：
00001：先手必赢 ，000010：先手必败
00011：先手必赢， 000100：先手必败………………
找到规律接近根的地方为1，先手必赢，否则必败
根据博弈组合游戏，那么答案就是包含x点的边权的异或和来判断先手是否能赢
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long ll;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 1e5+10, maxn = 1e3+20, inf = 2e9;struct edge{ int v,w; int nex;}edge[N];int head[N];int edg;void init(){ memset(head,-1,sizeof(head)); edg=0;}void add(int u,int v,int w){ edg++; edge[edg].v=v; edge[edg].w=w; edge[edg].nex=head[u]; head[u]=edg;}int main(){ int T; scanf("%d",&T); while(T--) { init(); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } while(m--) { int hh; scanf("%d",&hh); if(hh==0) { int x; scanf("%d",&x); int ANS=0; for(int i=head[x];i!=-1;i=edge[i].nex) { int w=edge[i].w; ANS^=w; } if(ANS) printf("Girls win!\n"); else printf("Boys win!\n"); } else { int u,v,w; scanf("%d%d%d",&u,&v,&w); for(int i=head[u];i!=-1;i=edge[i].nex) { if(edge[i].v==v) { edge[i].w=w; break; } } for(int i=head[v];i!=-1;i=edge[i].nex) { if(edge[i].v==u) { edge[i].w=w; break; } } } } } return 0;}
1005：
假设我们确定了前两列的状态，那么整个行列就可以O（n）推出来了
枚举状态就好了
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define ls i<<1 #define rs ls | 1 #define mid ((ll+rr)>>1) #define pii pair<int,int> #define MP make_pair typedef long long LL; const long long INF = 1e18+1LL; const double Pi = acos(-1.0); const int N = 1e4+10, maxn = 1e3+20, inf = 2e9; const LL mod = 100000000+7; int n; char a[N]; int b[N]; LL cc(int x){ if(x==0||x==2) return 1ll; return 2ll; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s",a); n=strlen(a); for(int i=0;i<n;i++) a[i]-=‘0‘; if(n==1){ if(a[0]==1) puts("2"); else if(a[0]==0||a[0]==2) puts("1"); else puts("0"); continue; } LL ans=0; for(int x=0;x<=min(2,(int)a[0]);x++){ ///printf("x = %d\n",x); LL sum=1; if(a[0]-x>2||a[0]-x<0) continue; b[0]=a[0]-x,b[1]=x; sum=sum*cc(b[0])%mod,sum=sum*cc(b[1])%mod; for(int i=2;i<n;i++){ b[i]=a[i-1]-b[i-1]-b[i-2]; if(b[i]<0||b[i]>2) {sum=0;break;} sum=sum*cc(b[i])%mod; } if(b[n-1]+b[n-2]!=a[n-1]) sum=0; ans=(ans+sum)%mod; ///printf("%d %d sum = %lld\n",a[0]-x,x,sum); } printf("%lld\n",ans); } return 0; }
1008：
n只有100，预处理n^2出每段区间的异或和
那么查询的时候就二分找最近的值
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double Pi = acos(-1.0);const int N = 1e5+10, maxn = 1e3+20, mod = 1e9+7, inf = 2e9;struct ss{ int value,c;}mp[N];bool cmp(ss s1,ss s2) { if(s1.value =http://www.mamicode.com/= s2.value) return s1.c>s2.c; else return s1.value < s2.value;}int n,sum[N],a[N],cnt,san[N];map<int,int > H;int main() { int T; scanf("%d",&T); while(T--) { cnt = 0; scanf("%d",&n); H.clear(); for(int i =1; i<=n; ++i) scanf("%d",&a[i]),sum[i]=sum[i-1]^a[i]; for(int i = 1; i <= n; ++i) { for(int j = i; j <= n; ++j) { if(H[sum[j]^sum[i-1]]) { mp[H[sum[j]^sum[i-1]]].c = max(j-i+1,mp[H[sum[j]^sum[i-1]]].c); } else { mp[++cnt].value = http://www.mamicode.com/sum[j]^sum[i-1]; mp[cnt].c = j-i+1; H[sum[j]^sum[i-1]] = cnt; } } } sort(mp+1,mp+cnt+1,cmp); for(int i = 1; i <= cnt; ++i) { san[i] = mp[i].value; } int m,x; scanf("%d",&m); while(m--) { scanf("%d",&x); if(x <= san[1]) { printf("%d\n",mp[1].c); continue; } if(x >= san[cnt]) { printf("%d\n",mp[cnt].c); continue; } int pos1 = lower_bound(san+1,san+1+cnt,x) - san; int pos2 = pos1-1; if(abs(san[pos1]-x) < abs(san[pos2] - x)) { printf("%d\n",mp[pos1].c); } else if(abs(san[pos1]-x) > abs(san[pos2] - x)) printf("%d\n",mp[pos2].c); else printf("%d\n",max(mp[pos1].c,mp[pos2].c)); } printf("\n"); } return 0;}
1009：
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;int a[110];ll check(ll x){ int sum=0; while(x) { sum++; x/=2; } return sum;}int main(){ int T; scanf("%d",&T); while(T--) { ll l,r; scanf("%lld%lld",&l,&r); int L=check(l); int R=check(r); if(L!=R) { printf("%lld\n",(1ll<<max(L,R))-1); } else { if(L==0) { puts("0"); continue; } int ps=L-1; int cnt=0; while((l&(1ll<<ps))==(r&(1ll<<ps))&&ps>=0){ a[++cnt]=(l&(1ll<<ps))>>ps; ps--; } for(int i=cnt+1;i<=L;i++) a[i]=1; ll ans=0; for(int i=1;i<=L;i++) ans=ans*2ll+1ll*a[i]; printf("%lld\n",ans); } } return 0;}
2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）(5/10)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。