LDU20级新生排位赛第三场
pick一波出题人：
A. 小明的火柴
思路：
无论是组成矩形还是组成正方形，所需要的都是两条一样的边，甚至可能更多。
所以用map记录一下出现的次数，如果%4==2的话，就是两条一样的边。如果%4 == 0的话，就是四条一样的边。
最后判断一下就可以了。
int main(){ int n=read; map<int,int>mp; int cnt2=0,cnt4=0; for(int i=1;i<=n;i++){ int x=read; mp[x]++; if(mp[x]%4==2) cnt2++; if(mp[x]%4==0) cnt4++,cnt2--; } int m=read; while(m--){ char op[4]; cin>>op; int x=read; if(op[0]=='+'){ mp[x]++; if(mp[x]%4==2) cnt2++; if(mp[x]%4==0) cnt4++,cnt2--; } else{ mp[x]--; if(mp[x]%4==1) cnt2--; if(mp[x]%4==3) cnt4--,cnt2++; } //cout<<cnt2<<" "<<cnt4<<endl; if(cnt4>=2) puts("YES"); else if(cnt4==1&&cnt2>=2) puts("YES"); else puts("NO"); } return 0; }
B. Fox的阶乘
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e5+7; int a[maxn]; int main() { int n; int cnt=0; cin>>n; for(int i=1;i<=n;i++) a[i]=i; for(int i=1;i<=n;i++) { if(a[i]%5==0) { while(a[i]%5==0) { a[i]/=5; cnt++; } } } for(int i=1;i<=n;i++) { if(a[i]%2==0) { while(a[i]%2==0&&cnt>0) { a[i]/=2; cnt--; } } } int sum=1; for(int i=1;i<=n;i++) { sum=(sum*a[i])%10; } cout<<sum<<endl; }
C. 如何优雅的筛筛筛
typedef long long ll; const int N = 1e6 + 10; int cnt; int f[N]; bool vis[N]; int prime[N]; void init(const int n) { f[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { f[i] = i; prime[++cnt] = i; } for (int j = 1; j <= cnt && i <= n / prime[j]; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) { f[i * prime[j]] = f[i]; break; } f[i * prime[j]] = f[i] * f[prime[j]]; } } } int main() { init(1e6); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) printf("%d ", f[i]); return 0; }
D. 如何优雅的写代码
暴力能过，字典树也可以。
E. 小明同学喜欢的数
F. 最简单的签到题
单点修改，区间求和。
树状数组or线段树。
G. 生日聚会
double cnt,sum,ans; int main() { double n; cin>>n; ans=1.0; cnt=1.0; while(ans>=0.5000) { ans*=(1-cnt/n); cnt++; } cout<<cnt-1<<endl; return 0; }
H. 光签题
思路：
考虑每个点的贡献，假设该点的度数为x，那么该点的贡献为x*(x-1)/2。
度数为x说明和该点相邻的点有x个，从这x点中任选两个都是满足题意的，根据组合数学原理可知答案。
代码：
int n; int in[maxn]; int main(){ scanf("%d",&n); int a,b; for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); in[a]++; in[b]++; } ll ans=0; for(int i=1;i<=n;i++){ ans+=(in[i]*(in[i]-1))/2; } printf("%lld\n",ans); }
