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
",ans);
}