T1 与(and)

题目在这

Solution

从最高位开始搜，假设当前搜到i位，如果有两个以上的数第i位是1，那么Answer的第i位肯定是1，把这位不是1的数都去掉，继续往下搜，在这个过程中更新Answer。

#include<iostream> #include<cstdio> #include<cstring> inline long long read(){long long 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<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; } #define MN 300005 long long n,a[MN],cnt,ans; int main(){freopen("and.in","r",stdin);freopen("and.out","w",stdout);n=read();register int i,j,k;for(i=1;i<=n;i++) a[i]=read();for(j=30;j>=0;j--){cnt=0;for(i=1;i<=n;i++) if((a[i]>>j)&1) cnt++;if(cnt>=2){for(i=1,k=0;i<=n;i++) if((a[i]>>j)&1) a[++k]=a[i];ans+=(1<<j);n=cnt;}}printf("%lld\n",ans);return 0; }

T2 计数(count)

题目在这

Solution

记f[i][j]表示有i位、各位数之和是j的数量。

显然，前n位之和与后n位之和相等的数和奇数位之和与偶数位之和相等的均有
\[ \sum_{i=0}^M f_{n,i} \ \ \ \ \ \ (其中M表示n位数的各位数之和的最大值） \]
把两者相加，再减去同时满足两个条件的数的数量。

我们设前n位的奇数位和为a，偶数位为b；后n位的奇数位和位c，偶数位和为d。

所以 $ a+b=c+d $并且 $ a+c=b+d $ 所以 $ a=c $ 并且$ b=d$。

那么这部分的方案数等于：
\[ \sum_{i=0}^M f_{n/2,i}* \sum_{j=0}^M f_{(n+1)/2,j} \]

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mod 999983 int n,cc,s[15],ans,a,b; int f[1005][9005]; char S[15]; inline void add(int &x,long long y){x+=y;while(x>=mod) x-=mod;} inline void minus(int &x,long long y){x-=y;while(x<0) x+=mod;} int main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d%s",&n,S+1);cc=strlen(S+1);register int i,j,k;for(i=1;i<=cc;i++) s[i]=S[i]-'0';std::sort(s+1,s+cc+1);f[0][0]=1;int MAX=s[cc]*n;for(i=0;i<n;i++)for(j=0;j<=MAX;j++)if(f[i][j]>0){for(k=1;k<=cc;k++) add(f[i+1][j+s[k]],f[i][j]);}for(i=0;i<=MAX;i++) add(ans,((2LL)*f[n][i]*f[n][i])%mod);int len1=n>>1,len2=n+1>>1;MAX=s[cc]*len2;for(i=0;i<=MAX;i++){add(a,(1LL*f[len2][i]*f[len2][i])%mod);add(b,(1LL*f[len1][i]*f[len1][i])%mod);}printf("%d\n",(ans-(1LL*a*b)%mod+mod)%mod);return 0; }

T3 三角形(triangle)

题目在这

Solution

题目即判断链上是否存在a[x]+a[y]>a[z]

将链上的权值取出来排序，只需要判断是否有b[i]+b[i+1]>b[i+2]

如果都不满足，则有b[i+2]>=b[i]+b[i+1]，则b[i]至少会以斐波那契数列增长的速度增长

那么如果链的长度超过一定值（O(log 2^31)级别），必然存在合法的三元组

如果不超过，暴力判断即可

注意：会爆int

#include<cstdio> #include<cstring> #include<algorithm> inline long long read(){long long 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<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; } #define MN 100005 int n,m,a[MN],dep[MN],f[MN]; int Sort[MN],cnt; struct edge{int to,nex; }e[MN<<1];int hr[MN],pin; inline void ins(int f,int t){e[++pin]=(edge){t,hr[f]};hr[f]=pin;e[++pin]=(edge){f,hr[t]};hr[t]=pin; } inline void dfs(int fa,int x){f[x]=fa;dep[x]=dep[fa]+1;register int i;for(i=hr[x];i;i=e[i].nex)if(e[i].to^fa)dfs(x,e[i].to); } inline bool solve(int x,int y){cnt=0;while(x!=y){if(dep[x]<dep[y]) std::swap(x,y);Sort[++cnt]=a[x];x=f[x];if(cnt>50) return 1;}Sort[++cnt]=a[x];if(cnt>50) return 1;std::sort(Sort+1,Sort+cnt+1);for(register int i=3;i<=cnt;i++)if(Sort[i]<1LL*(Sort[i-1])+Sort[i-2])return 1;return 0; } int main(){freopen("triangle.in","r",stdin);freopen("triangle.out","w",stdout);n=read();m=read();register int i,x,y,v;for(i=1;i<=n;i++) a[i]=read();for(i=1;i<n;i++)x=read(),y=read(),ins(x,y);dfs(0,1);while(m--){v=read();x=read();y=read();switch(v){case 1:a[x]=y;break;case 0:puts(solve(x,y)?"Y":"N");break;}}return 0; }

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/9497179.html

总结

以上是生活随笔为你收集整理的[20180818]校内模拟赛的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。