「codechef」February Lunchtime 2015
懒得开多篇了
这题在逗我么
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #define ll long long #define inf 1000000000 #define mod 1032992941 #define N 500005 using namespace std; 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 n; char ch[100005]; int main() { n=read(); while(n--) { scanf("%s",ch+1); int l=strlen(ch+1),ans=0; for(int i=1;i<=l;i++) if(ch[i]=='4') ans++; printf("%d\n",ans); } return 0; } |
发现实际上把一个东西移动到一个位置
相当于不断做代价为1的交换
所以只要枚举给3种字母赋权，求逆序对最小值即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #define ll long long #define inf 1000000000 #define mod 1032992941 #define N 500005 using namespace std; 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; } ll mn; int n,l; char ch[100005]; int v[1005],a[100005],num[5]; void solve() { ll ans=0; memset(num,0,sizeof(num)); for(int i=1;i<=l;i++) a[i]=v[ch[i]]; for(int i=1;i<=l;i++) { num[a[i]]++; if(a[i]==2)ans+=num[3]; if(a[i]==1)ans+=num[2]+num[3]; } mn=min(mn,ans); } int main() { n=read(); while(n--) { scanf("%s",ch+1); l=strlen(ch+1);mn=1e60; v['r']=1;v['g']=2;v['b']=3;solve(); v['r']=1;v['g']=3;v['b']=2;solve(); v['r']=2;v['g']=1;v['b']=3;solve(); v['r']=2;v['g']=3;v['b']=1;solve(); v['r']=3;v['g']=1;v['b']=2;solve(); v['r']=3;v['g']=2;v['b']=1;solve(); printf("%lld\n",mn); } return 0; } |
设f[i][j]表示i为根的子树，后代到i经过轻边数量不超过j
树形dp，要用到前缀后缀积/逆元。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #define ll long long #define inf 1000000000 #define mod 19101995 #define N 100005 using namespace std; 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 n,cnt,m; int last[N]; ll f[N][25],s1[N],s2[N]; vector<int> st; struct edge{ int to,next; }e[2*N]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dp(int x,int fa) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa)dp(e[i].to,x); st.clear(); for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa)st.push_back(e[i].to); if(st.size()==0) { for(int j=0;j<=m;j++) f[x][j]=1; return; } else if(st.size()==1) { for(int j=0;j<=m;j++) f[x][j]=f[st[0]][j]; return; } for(int j=1;j<=m;j++) { s1[0]=s2[0]=1; for(int i=0;i<st.size();i++) { s1[i+1]=s1[i]*f[st[i]][j-1]%mod; s2[i+1]=s2[i]*f[st[st.size()-i-1]][j-1]%mod; } for(int i=0;i<st.size();i++) { f[x][j]=(f[x][j]+s1[i]*s2[st.size()-i-1]%mod*f[st[i]][j])%mod; } } } int main() { n=read();m=log(n)/log(2); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); } dp(1,0); printf("%d\n",f[1][m]); return 0; } |
一眼分解质因数。。。
这数据范围要用rho TAT
rho要配合素数测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<ctime> #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 500005 using namespace std; ll read() { ll 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; } ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int T,n; map<ll,int> mp; ll a[105]; ll mul(ll a,ll b,ll p) { a%=p;ll ans=0; for(ll i=b;i;i>>=1,a=(a+a)%p) if(i&1)ans=(ans+a)%p; return ans; } ll pow(ll a,ll b,ll p) { a%=p;ll ans=1; for(ll i=b;i;i>>=1,a=mul(a,a,p)) if(i&1)ans=mul(ans,a,p); return ans; } bool check(ll a,ll n,ll r,ll s) { ll ans=pow(a,r,n),p=ans; for(int i=1;i<=s;i++) { ans=mul(ans,ans,n); if(ans==1&&p!=1&&p!=n-1)return 1; p=ans; } if(ans!=1)return 1; return 0; } bool MR(ll n) { if(n<2)return 0; if(n==2)return 1; if(n%2==0)return 0; ll r=n-1,s=0; while(r%2==0){r/=2;s++;} for(int i=0;i<10;i++) { if(check(rand()%(n-1)+1,n,r,s)) return 0; } return 1; } ll rho(ll n,ll c) { ll k=2,x=rand()%n,y=x,d; for(ll i=1;i<=k;i++) { x=(mul(x,x,n)+c)%n; if(y==x)return n; d=gcd(n,abs(y-x)); if(d!=1&&d!=n) return d; if(i==k) { y=x;k+=k; } } } void solve(ll n) { if(n==1)return; if(MR(n)) { mp[n]++; return; } ll tmp=n; while(tmp==n)tmp=rho(n,rand()%(n-1)+1); solve(tmp); solve(n/tmp); } int main() { srand(time(NULL)); T=read(); while(T--) { mp.clear(); n=read();ll ans=1; for(int i=1;i<=n;i++) { a[i]=read(); ans=ans*(a[i]%mod)%mod; } for(int i=1;i<=n;i++) solve(a[i]); for(map<ll,int>::iterator i=mp.begin();i!=mp.end();i++) { i->second%=3; if(i->second) for(int j=i->second;j<3;j++) ans=(i->first%mod*ans)%mod; } printf("%lld\n",ans); } return 0; } |
Subscribe
计数器 9301347
OI 课件=>
OI 课件=>