Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined)
23:35～2:35 1.12.2017 |实际 23:35~1:40
题意：妙蛙种子太神了
题解：妙蛙种子太神了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=1e5+5,INF=1e9; int n,c[300],ans=INF; char s[N],a[20]="Bulbasaur"; int main(int argc, const char * argv[]) { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) c[s[i]]++; int len=strlen(a);//printf("ln %d %c\n",len,a[0]); for(int i=0;i<len;i++) ans=min(ans,c[a[i]]); ans=min(ans,min(c[‘a‘]/2,c[‘u‘]/2)); printf("%d",ans); return 0; }
题意：选尽量多的数使他们的gcd不为1
题解：
gcd不为1一定有一个公共质因子
然后就是用那个避免线性筛的常用技巧
vis[i]表示i这个数出现次数，枚举这个公共质因子，在枚举他的所有倍数，用vis[倍数]更新质因子为他时的答案
根据素数个数n/logn和调和级数复杂度为O(n)
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=1e5+5; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int n,a,vis[N],mx; int p[N],notp[N]; void sieve(int n){ for(int i=2;i<=n;i++){ if(!notp[i]) p[++p[0]]=i; for(int j=1;j<=p[0]&&i*p[j]<=n;j++){ notp[i*p[j]]=1; if(i%p[j]==0) break; } } } void solve(int n){ int ans=0,tmp=0; for(int j=1;j<=p[0];j++){ tmp=0; for(int i=p[j];i<=n;i+=p[j]) if(vis[i]) tmp+=vis[i]; ans=max(ans,tmp);//printf("hi %d %d\n",p[j],tmp); } printf("%d\n",ans==0?1:ans); } int main(int argc, const char * argv[]){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++) a=read(),vis[a]++,mx=max(mx,a); sieve(mx); solve(mx); return 0; }
注意：没注意多个数相同WA一次，没特判一个数WA一次，i打成了a最终结果没过，SAD
题意：自己看
题解：
一下子就想到了，在每个gym里都相同才可以互换，然后可以互换的求全排列再乘法原理
然后就开始想怎么求在每个gym里都相同，也许是太晚了想了一个多小时还不会
其实很简单，用一个vector数组储存每种type在那些gym里出现过，出现多次就保存多个
然后把这些vector排序，用离散化去重的方法统计答案就行了
vector也是按字典序比较的
这种保存出现位置的做法和这道题有点类似吧
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N=1e6+5,MOD=1e9+7; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int n,m; vector<int> v[N]; int main(){ //freopen("in.txt","r",stdin); n=read();m=read(); for(int i=1;i<=n;i++){ int g=read(); while(g--) v[read()].push_back(i); } sort(v+1,v+1+m); ll _=1,ans=1; for(int i=2;i<=m;i++){ if(v[i]==v[i-1]) ans=(ans*(++_))%MOD; else _=1; } printf("%d",ans); }
Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) 【未完待续】
原文：http://www.cnblogs.com/candy99/p/6284051.html
