link I use the link's code, but generate code like this Your text to link here... I don't know why? The DEFAULTMAIN seems unused and the testcode is c++ style
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
link I use the link's code, but generate code like this Your text to link here... I don't know why? The DEFAULTMAIN seems unused and the testcode is c++ style
T_T....
recently , I'm learning the KM algorithm , after read some resources on the internet,I still can't fully understand ,do you guys have any paper or some useful information to help me ..many thanks
Cows and Cool Sequences maybe this proof is easy for you ,but for me .... hehe....so I wrote this ... my english is so poor,so i can't understand the Tutorial I think most of you can come up with the idea of DP,but be confused with the proof of how to judge whether a cool sequence can begin with a[i] and ends with a[j] . Proof: first : a conclusion
if(x,y) is cool
if(y is odd) then x%y=0
else (2*x%y==0 && x%y!=0)
proof : provided that the first number of the sequence is t ,so
x = y*(y-1)/2 + y * t
if y is odd, ( y — 1) is even ,so x = y*((y-1)/2+t),so if (x,y) is cool x must be divided by y if y is even, y-1 is odd so
2*x = y*(y-1) + 2*y*t ;
2*x = y*( (y-1)+2*y*t );
so 2*x must be divided by y ,but another x can't be divided by y(because 2*y*t is odd)
and there is also another important conclusion when y is even ,that is m[y] = m[x] + 1; (m[n] denote the exponent of the largest power of 2 that divides n.) this is also easy to prove :
a[i] = 2^a * p
2*a[i] = 2^(a+1)*p
a[j] = 2^b*q
(p,q are the biggest odd factor )
since a[j] can divided 2*a[i] and a[j] can't divided a[i],we can conclude b = a + 1;
we can solve the problem , no matter what's the parity of a[j] , there's a big condition must be fullfilled:
the max odd factor of a[i] must be divided by the max odd factoe of a[j]
if a[j] is odd ,and a[i]%a[j]==0,we can always construct the sequence
,for example a[i]=12 a[j] = 3,we can construct the sequence like
12 3 ...3 3 3 3 3 3 3 3.
if a[j] is even , given that m[u] = m[u-1] + 1. so m[j] = m[i] + j — i; it's the situation that all of the numbers in the cool sequence(except a[i]) are even
for example :a[i] = 3,a[j] = 36 ,the sequence is : 3 6 12 24 36
the last situation is there are some odd numbers in the left part of the sequence ,and then even numbers ..
what's the condition of this situation that ensures there's a cool sequence ? it's easy now :
m[j] <= j -i - 1;
for example : a[i] = 6,a[j] = 24; cool sequence : 6 3 3 3 3 6 12 24
if m[j] > j — i — 1,there can't be any cool sequence begins with a[i],ends with a[j]. because m[i+1] = m[j] — (j — i -1) > 0 since a[i],a[i+1] must be cool and a[i+1] is even ,so
m[i+1] = m[j] - j - i - 1
m[i] < m[i+1] , m[i]+1 >= m[j]-(j-i-1)
so m[i] == m[j] - (j-i) -> m[i] + j - i = m[j]
(so here coms a contradiction ,it's already judged in the case up )
Recently I suffered alot of problems about java,so can anyone give me some good websites to learn by myself?
http://www.codeforces.com/contest/59/problem/E mother always tell me when you fail , just try again and again ,but i'm keep failing — -
kawatea's solution http://codeforces.net/contest/246/submission/2621642 i think it's brute force because this solution uesd a "for" loop to find distinct names of k sons
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int inf = ~0u>>2;
int c3,c4,c5,k3,k4,k5;
int F(){
return abs(c3*k3-c4*k4)+abs(c4*k4-c5*k5);
}
int main()
{
int n,s,i,j,k;
scanf("%d%d",&n,&s);
for(c3=c4=c5=0;n;n--)
{
scanf("%d",&j);
if(j==3) c3++;
if(j==4) c4++;
if(j==5) c5++;
}
int ans=inf,x,y,z;
for(k3=s/(c3+c4+c5);k3>=0;k3--)
{
int up=inf;
for(k4=(s-k3*c3)/(c4+c5);k4>=k3;k4--)
{
k5=(s-c3*k3-k4*c4);if(k5%c5) continue;
k5/=c5;
if(k5<k4 ) continue;
int tmp=F();
if(tmp<up)
{
up=tmp;
if(up<ans)
{
ans=up;
x=k3;y=k4;z=k5;
}
}
else break;//where is the monotonicity
//why can we use break here,I can't understand
}
}
if(ans==inf) printf("-1\n");
else printf("%d %d %d\n",x,y,z);
}
using namespace std; const int inf = ~0u>>2; int c3,c4,c5,k3,k4,k5; int F(){ return abs(c3*k3-c4*k4)+abs(c4*k4-c5*k5); } int main() { int n,s,i,j,k; scanf("%d%d",&n,&s); for(c3=c4=c5=0;n;n--) { scanf("%d",&j); if(j==3) c3++; if(j==4) c4++; if(j==5) c5++; } int ans=inf,x,y,z; for(k3=s/(c3+c4+c5);k3>=0;k3--) { int up=inf; for(k4=(s-k3*c3)/(c4+c5);k4>=k3;k4--) { k5=(s-c3*k3-k4*c4);if(k5%c5) continue; k5/=c5; if(k5<k4 ) continue; int tmp=F(); if(tmp<up) { up=tmp; if(up<ans) { ans=up; x=k3;y=k4;z=k5; } } else break;//where is the monotonicity //why can we use break here,I can't understand } } if(ans==inf) printf("-1\n"); else printf("%d %d %d\n",x,y,z); }
I can't understand the solutions of the accepted code
CF 191B
#include<cstdio>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 lld;
multiset<int> Q;
int a[100010];
int main()
{
int n,k,i;
lld sum=0,b;
scanf("%d%d",&n,&k);
scanf("%I64d",&b);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=n;
for(i=n-k+1;i<n;i++)
{
sum+=a[i];
Q.insert(a[i]);
}
for(i=n-k;i>=1;i--){
sum+=a[i];
if(sum>b) ans=i;
Q.insert(a[i]);
int tmp=*Q.begin();
sum-=tmp;
Q.erase(Q.begin());//it's wrong if I erase the key number like Q.erase(tmp),it may erase many numbers
}
printf("%d\n",ans);
return 0;
}
Name |
---|