Manthan, Codefest 16
A. Ebony and Ivory
给定a，b，c
求一组整数解x，y使得x * a + y * b = c
题解
数据范围很小暴力枚举x
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long 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; } int a,b,c; int main() { a=read();b=read();c=read(); for(int i=0;i<=10000;i++) { int t=c-a*i; if(t<0)break; if(t%b==0) { puts("Yes"); return 0; } } puts("No"); return 0; } |
B. A Trivial Problem
求n！有多少个0
题解
暴力求n！被多少个2和5整除
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long 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; } int m,K; int t2,t5; int ans[500005]; int main() { m=read(); for(int i=1;i<=500000;i++) { int t=i; while(t%2==0)t/=2,t2++; while(t%5==0)t/=5,t5++; if(min(t2,t5)==m)ans[++K]=i; } printf("%d\n",K); for(int i=1;i<=K;i++) printf("%d ",ans[i]); return 0; } |
C. Spy Syndrome 2
给定长为（n <= 10000）的主串，给（m <= 100000）个长不超过1000的子串，总长不超过1000000
求一个主串由 子串的反串 拼出的解法
题解
求每个子串的哈希值，主串每位枚举串长 <= 1000，求出哈希值和子串进行匹配转移
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long 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; } int n,m; char a[10005],ch[1005]; string b; ll f[10005]; map<ll,string> mp; int main() { n=read(); scanf("%s",a); m=read(); for(int i=1;i<=m;i++) { scanf("%s",ch);b=""; int l=strlen(ch); for(int j=0;j<l;j++)b+=ch[j]; ll h=0; for(int j=l-1;j>=0;j--) h=h*31+tolower(b[j]); mp[h]=b; } f[n]=1; for(int i=n-1;i>=0;i--) { ll h=0; for(int j=1;j<=1000&&i+j<=n;j++) { h=h*31+a[i+j-1]; if(mp.count(h)&&f[i+j]) { f[i]=h; break; } } } for(int i=0;i<n;i+=mp[f[i]].length()) cout<<mp[f[i]]<<' '; return 0; } |
D. Fibonacci-ish
给一个长为( n <= 1000 )的数列，数字 <= 10^9 问最多能选出多少个数组成广义斐波那契数列
题解
枚举选出两个作为斐波那契数列的开头，暴力递推，由于斐波那契数列的增长速度很快，几十项就会超过10 ^ 9
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long 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; } int n,mx; int a[1005]; map<int,int> mp; vector<int> q; void solve(int x,int y) { int ans=2; if(x==0&&y==0)return; mp[x]--;mp[y]--; q.push_back(x); q.push_back(y); while(1) { int z=x+y; if(mp[z]) { ans++; mp[z]--; q.push_back(z); } else break; x=y;y=z; } mx=max(mx,ans); for(int i=0;i<q.size();i++) mp[q[i]]++; q.clear(); } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) mp[a[i]]++; mx=mp[0]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) solve(a[i],a[j]); printf("%d\n",mx); return 0; } |
F. The Chocolate Spree
在树上选两条不相交的链，使链上的点权和最大
预处理
best[x]表示x子树内的最长链
down[x]表示子树内从x出发的最长链
up[x]表示从x出发，终点在x子树外的最长链
最终一定存在点，使得最优解的一条链 a 经过它，另一条链 b 在它的一个儿子的子树内且链 a 不经过这个儿子
枚举这个儿子y，答案就是best[y]加上链 a
链 a 有若干种情况，记录down的前后缀最大/次大值讨论一下即可
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long 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; } int n; ll ans; ll a[100005]; ll down[100005],best[100005],up[100005]; ll ld[100005],rd[100005],ld2[100005],rd2[100005],rb[100005]; vector<int> e[100005]; void pre(int x,int fa) { int n=e[x].size(); down[x]=a[x]; for(int i=0;i<n-1;i++) { if(e[x][i]==fa)swap(e[x][i],e[x][n-1]); int y=e[x][i]; pre(y,x); best[x]=max(best[x],best[y]); best[x]=max(best[x],down[x]+down[y]); down[x]=max(down[x],down[y]+a[x]); } best[x]=max(best[x],down[x]); } void pre2(int x) { int n=e[x].size();n--; rd[n+1]=0;ld[0]=0; for(int i=1;i<=n;i++) ld[i]=max(ld[i-1],down[e[x][i-1]]); for(int i=n;i>=1;i--) rd[i]=max(rd[i+1],down[e[x][i-1]]); for(int i=1;i<=n;i++) { int y=e[x][i-1]; up[y]=up[x]+a[y]; up[y]=max(up[y],ld[i-1]+a[x]+a[y]); up[y]=max(up[y],rd[i+1]+a[x]+a[y]); } for(int i=0;i<n;i++) pre2(e[x][i]); } void dp(int x) { int n=e[x].size();n--; for(int i=0;i<n;i++) dp(e[x][i]); rd[n+1]=rd2[n+1]=rb[n+1]=0; ld[0]=ld2[0]=0; for(int i=1;i<=n;i++) { int y=e[x][i-1]; ld[i]=ld[i-1];ld2[i]=ld2[i-1]; if(down[y]>ld[i]) ld2[i]=ld[i],ld[i]=down[y]; else ld2[i]=max(ld2[i],down[y]); } for(int i=n;i>=1;i--) { int y=e[x][i-1]; rb[i]=max(rb[i+1],best[y]); rd[i]=rd[i+1];rd2[i]=rd2[i+1]; if(down[y]>rd[i]) rd2[i]=rd[i],rd[i]=down[y]; else rd2[i]=max(rd2[i],down[y]); } for(int i=1;i<=n;i++) { int y=e[x][i-1]; ll now=max(rb[i+1],up[x]+max(ld[i-1],rd[i+1])); now=max(now,ld[i-1]+ld2[i-1]+a[x]); now=max(now,rd[i+1]+rd2[i+1]+a[x]); now=max(now,ld[i-1]+rd[i+1]+a[x]); ans=max(ans,now+best[y]); } } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); } e[1].push_back(0); pre(1,0); up[1]=a[1];pre2(1); dp(1); cout<<ans<<endl; return 0; } |
计数器 9874354
OI 课件=>
OI 课件=>
Orz
黄学长，你发Saber的图干甚，脑子没坑啊！
请说话得体
图在哪里啊=-=
请注意您的用词啊=-=
起码人家有脑子，可惜你没有
0w0 这位同学我只看到你头像有Saber。。。
活捉。。。高三了竟然还能看到。
话说图片到底放在哪呢，看见喵帕斯就戳进来了然而并没有，如何做到的？
来晚了，又匿了TAT
QwQ
每次看到都不一样诶，好神奇
你是说搜索引擎收录的时候会抓取页面的图片么。？
我没看到过哪有喵帕斯啊
指的就是首页每篇博文的配图啊
找到了
图包2014-12-05_10-13-41&2014-12-05_10-14-06
随机显示？
另外图就THx了（＾∀＾）