500pt,
题目链接:http://codeforces.com/problemset/problem/371/A
分析:k-periodic说明每一段长度为k,整个数组被分成这样长度为k的片段,要使得修改最少,求出k长度的片段中每个位置出现次数最多的数就行。
代码:
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <string.h> using namespace std; int n,k; int input[110]; map<int,int> m[110]; int right1[110]; int findMax(map<int,int> m) { int index = 0; int cnt = 0; map<int,int>::iterator it = m.begin(); for(;it!=m.end();it++) { if(it->second>cnt) { cnt = it->second; index = it->first; } } return index; } int main() { while(cin>>n>>k) { memset(input,0,sizeof(input)); memset(right1,0,sizeof(right1)); for(int i=0;i<k;i++) m[i].clear(); for(int i=0;i<n;i++) cin>>input[i]; for(int i=0;i<n;i++) { m[i%k][input[i]]++; } for(int i=0;i<k;i++) { right1[i] = findMax(m[i]); } int ret = 0; for(int i=0;i<n/k;i++) { for(int j=0;j<k;j++) { if(input[i*k+j]!=right1[j]) ret++; } } cout<<ret<<endl; } return 0; }
1000pt: 题目链接:http://codeforces.com/problemset/problem/371/B
题目分析:将每个数都除以2,3,5直到不能再除,如果最后数不一样就返回-1,一样就根据除的次数返回,具体看代码,这题我也是看了别人代码明白过来的
代码:
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <string.h> using namespace std; int a,b; int ret; void div(int p) { int cnta = 0; int cntb = 0; while(a%p==0&&a>0) { cnta++; a/=p; } while(b%p==0&&b>0) { cntb++; b/=p; } ret += abs(cnta-cntb); } int main() { while(cin>>a>>b) { ret=0; div(2); div(3); div(5); cout<<(a==b?ret:-1)<<endl; } return 0; }
1500:题目链接:http://codeforces.com/problemset/problem/371/C
分析:不要直接模拟计算会超时,直接二分查找,0-1e14,看哪个最能满足条件
代码:
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <string.h> using namespace std; string s; int nb1,ns1,nc1;//做一份需要的数量 int nb,ns,nc;//目前有的数量 int pb,ps,pc;__int64 r;//价格 bool ok(__int64 m) { __int64 bneed = (m*nb1<=nb)?0:(m*nb1-nb)*pb; __int64 sneed = (m*ns1<=ns)?0:(m*ns1-ns)*ps; __int64 cneed = (m*nc1<=nc)?0:(m*nc1-nc)*pc; __int64 need = bneed+sneed+cneed; if(r>=need) return true; else return false; } int main() { while(cin>>s) { nb1=0;ns1=0;nc1=0; for(int i=0;i<s.length();i++) { if(s[i]=='B') nb1++; if(s[i]=='S') ns1++; if(s[i]=='C') nc1++; } cin>>nb>>ns>>nc; cin>>pb>>ps>>pc>>r; __int64 ll=0,rr=1e14; while(ll<=rr-1) { __int64 mid = (ll+rr+1)/2; if(ok(mid)) { ll = mid; } else { rr = mid-1; } } cout<<ll<<endl; } return 0; }