scu集训队第一回周赛记录
scu集训队第一次周赛记录
A题：凯牛4分41秒出的题，我用了一个小时，正确思路是：把这个数n分解成i个4，和j个7的和，并且7的个数要尽量多才能才能使位数最少（毕竟要至少两个4的和才能大于7），然
后输出的时候把全部4输出在前，全部7输出在后。我用了较长时间就是用刚好装满的完全背包来将n分解为i个4和j个7的和，事实上暴力也能过。。。。
我的代码：
暴力代码（暴力62ms，我的30ms）：
第一次周赛，集训队老队员和新队员混合比赛，但是本周全是模拟题，没有具体算法，几个大牛都是AK。见到了久仰得凯牛真身，只能不停远远地orzorz。五道题，我两小时除了前
四题，最后时间全部耗费在最后一题上，无果。
A题：凯牛4分41秒出的题，我用了一个小时，正确思路是：把这个数n分解成i个4，和j个7的和，并且7的个数要尽量多才能才能使位数最少（毕竟要至少两个4的和才能大于7），然
后输出的时候把全部4输出在前，全部7输出在后。我用了较长时间就是用刚好装满的完全背包来将n分解为i个4和j个7的和，事实上暴力也能过。。。。
B题：只有18种回文时间，打表即可。
C题：模拟一下就ok，但是wa了几次，没有认真的读懂题得没一句话，这样赶时间是得不偿失去的！！以后读题一定要仔细仔细仔细！
D题：模拟，对空格有要求。
E题赛场上想用排序优化时间效率，找出最小消耗所对应的那个数，但是没有想到怎样对原数组改变这个数并字典序输出。比赛后简单听了李大神字典序输出的思路，下来想了下，改
了下过了。
我的思路：先对整个序列排序，然后从0到9枚举要改变的数字，看他们打到要求的最小消耗是多少。枚举方法是，找到该数字在序列中左端第一个出现的位置i和右端第一个出现的位
置j，然后分别向左右延伸，这里延伸左边还是右边要看左边或右边第一个数字和该数字的差越小越先，然后当j-i+1 >= k是跳出枚举。这样就可以找出每一个数字达到最小要求的消
耗了。这里直接找出最小消耗数字，进行字典序输出即可，后来wa了几发，原来当存在多个数字的最小消耗相同时，要考虑到底采用哪一个数字。
比如测试数据：
8 4
22294777
其中7和2的最小消耗都是2，显然改变7的22274777比改变2的22292777字典序小。这样对于几个相同消耗的数字就应该选择到底保留哪一个？我得选择方法是哪个数先出现变为该数的
大数，且大数靠左就选择该数。
然后考虑是字典序输出：从左到右扫描大于该数的数变小为该数，从右向左扫描小于该数的数变为该数，直到满足条件扫描结束。（注意其中内涵的原理，对于某一个数字i有可能不
需要把它全变为目标相同数字，当i大于目标相同数字，就让左边的改变，对于i小于目标数字就让右边的改变）
网上简介思路：没有必要，直接0到9暴力统计，并记下满足条件的最小字符串，最后比较9个字符串输出即可！！当时比赛的时候不敢来就暴力，毕竟惧怕超时。没有仔细考虑复杂度
！k只有1e4，就算全部枚举也才1e5！！
第一次周赛，集训队老队员和新队员混合比赛，但是本周全是模拟题，没有具体算法，几个大牛都是AK。见到了久仰得凯牛真身，只能不停远远地orzorz。五道题，我两小时除了前四题，最后时间全部耗费在最后一题上，无果。如果我考虑到E题数据限制低，暴力可过，或许是能ac的！
心得：
1.读题一定要理智，慢，读懂每一句话，不要慌忙出题。想好方法，简单的方法再写代码，会比乱写一堆然后调试半天好得多。
A题：凯牛4分41秒出的题，我用了一个小时，正确思路是：把这个数n分解成i个4，和j个7的和，并且7的个数要尽量多才能才能使位数最少（毕竟要至少两个4的和才能大于7），然
后输出的时候把全部4输出在前，全部7输出在后。我用了较长时间就是用刚好装满的完全背包来将n分解为i个4和j个7的和，事实上暴力也能过。。。。
我的代码：
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 1009
#define INF 1e9
using namespace std;
struct pal{int x,c4,c7;}F[1000009];
int main(void){
int n,c4,c7;
while(~scanf("%d",&n)){
c4=c7=0;
for(int i=0;i <= n;i++) {
F[i].x=-1000;
F[i].c4=F[i].c7=0;
}
F[0].x=0;
for(int j=4;j <= n;j++){
if(j-7 >= 0){
if(F[j-4].x+4 > 0 || F[j-7].x+7 > 0 )
if(F[j].x < F[j-4].x+4 || F[j].x < F[j-7].x+7 ){
if(F[j-4].x+4 > F[j-7].x+7) {F[j].c4=F[j-4].c4+1;F[j].c7=F[j-4].c7;}
else {F[j].c7=F[j-7].c7+1;F[j].c4=F[j-7].c4;}
F[j].x=max(F[j-4].x+4,F[j-7].x+7);
}}else{
if(F[j-4].x+4 >= 0 && F[j].x < F[j-4].x+4){
F[j].c4=F[j-4].c4+1;
F[j].x=F[j-4].x+4;
if(j-7 >=0) F[j].c7=F[j-4].c7;
}
}
}
if(F[n].x != n) printf("-1\n");
else{
for(int i=0;i < F[n].c4;i++) printf("4");
for(int i=0;i < F[n].c7;i++) printf("7");
printf("\n");}
}
return 0;
}
暴力代码（暴力62ms，我的30ms）：
第一次周赛，集训队老队员和新队员混合比赛，但是本周全是模拟题，没有具体算法，几个大牛都是AK。见到了久仰得凯牛真身，只能不停远远地orzorz。五道题，我两小时除了前
四题，最后时间全部耗费在最后一题上，无果。
A题：凯牛4分41秒出的题，我用了一个小时，正确思路是：把这个数n分解成i个4，和j个7的和，并且7的个数要尽量多才能才能使位数最少（毕竟要至少两个4的和才能大于7），然
后输出的时候把全部4输出在前，全部7输出在后。我用了较长时间就是用刚好装满的完全背包来将n分解为i个4和j个7的和，事实上暴力也能过。。。。
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 1009
#define INF 1e9
using namespace std;
int main(void){
int n,c4,c7;
while(~scanf("%d",&n)){
c4=c7=0;
for(int i=0;i <= n/4;i++){
for(int j=0;j <= (n-i*4)/7;j++){
if(i*4+j*7 == n){
c4=i;
c7=j;
n=-11;
}
}
}
if( c4*c4 + c7*c7){
for(int i=0;i < c4;i++) printf("4");
for(int j=0;j < c7;j++) printf("7");
}else printf("-1");
printf("\n");
}
return 0;
}
B题：只有18种回文时间，打表即可。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#define M 1009
#define INF 1e9
using namespace std;
int str[16][2]={1,10,2,20,3,30,4,40,5,50,10,1,11,11,12,21,13,31,14,41,15,51,20,2,21,12,22,22,23,32,24,42};
int main(void){
int n,m;
while(~scanf("%d:%d",&n,&m)){
for(int i=0;i < 16;i++){
if((str[i][0] == n && str[i][1] > m) || (str[i][0] > n) ){
if(str[i][0] == 24) printf("00:00\n");
else printf("%.2d:%.2d\n",str[i][0],str[i][1]);
break;
}
}
}
return 0;
}
C题：模拟一下就ok，但是wa了几次，没有认真的读懂题得没一句话，这样赶时间是得不偿失去的！！以后读题一定要仔细仔细仔细！
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#define M 1009
#define INF 1e9
using namespace std;
int main(void){
char wang,n1,m1,n2,m2;
wang=getchar();
getchar();
scanf("%c%c %c%c",&n1,&m1,&n2,&m2);
if(n1 == 'T') n1='A';
else if(n1 == 'J') n1='B';
else if(n1 == 'Q') n1='C';
else if(n1 == 'K') n1='D';
else if(n1 == 'A') n1='E';
if(n2 == 'T') n2='A';
else if(n2 == 'J') n2='B';
else if(n2 == 'Q') n2='C';
else if(n2 == 'K') n2='D';
else if(n2 == 'A') n2='E';
if(m1 == wang && m2 != wang) printf("YES\n");
else if(m2 == wang && m1 != wang) printf("NO\n");
else if(m1 == m2 && n1 > n2) printf("YES\n");
else printf("NO\n");
return 0;
}
D题：模拟，对空格有要求。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#define M 1009
#define INF 1e9
using namespace std;
int main(void){
int n;
scanf("%d",&n);
for(int i=0;i <= 2*n;i++){
int k=i;
if(k > n) k=n-(i-n);
for(int j=1;j < 2*n-k*2;j++) printf(" ");
for(int ii=0;ii <=k;ii++){
if(!(k == n && !ii)) printf(" ");
printf("%d",ii);}
for(int ii=k-1;ii >=0;ii--) printf(" %d",ii);
printf("\n");
}
return 0;
}
E题赛场上想用排序优化时间效率，找出最小消耗所对应的那个数，但是没有想到怎样对原数组改变这个数并字典序输出。比赛后简单听了李大神字典序输出的思路，下来想了下，改
了下过了。
我的思路：先对整个序列排序，然后从0到9枚举要改变的数字，看他们打到要求的最小消耗是多少。枚举方法是，找到该数字在序列中左端第一个出现的位置i和右端第一个出现的位
置j，然后分别向左右延伸，这里延伸左边还是右边要看左边或右边第一个数字和该数字的差越小越先，然后当j-i+1 >= k是跳出枚举。这样就可以找出每一个数字达到最小要求的消
耗了。这里直接找出最小消耗数字，进行字典序输出即可，后来wa了几发，原来当存在多个数字的最小消耗相同时，要考虑到底采用哪一个数字。
比如测试数据：
8 4
22294777
其中7和2的最小消耗都是2，显然改变7的22274777比改变2的22292777字典序小。这样对于几个相同消耗的数字就应该选择到底保留哪一个？我得选择方法是哪个数先出现变为该数的
大数，且大数靠左就选择该数。
然后考虑是字典序输出：从左到右扫描大于该数的数变小为该数，从右向左扫描小于该数的数变为该数，直到满足条件扫描结束。（注意其中内涵的原理，对于某一个数字i有可能不
需要把它全变为目标相同数字，当i大于目标相同数字，就让左边的改变，对于i小于目标数字就让右边的改变）
网上简介思路：没有必要，直接0到9暴力统计，并记下满足条件的最小字符串，最后比较9个字符串输出即可！！当时比赛的时候不敢来就暴力，毕竟惧怕超时。没有仔细考虑复杂度
！k只有1e4，就算全部枚举也才1e5！！
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#define M 1009
#define INF 1e9
using namespace std;
int str[10009],str1[10009];
int main(void){
int n,k;
scanf("%d%d",&n,&k);
getchar();
for(int i=0;i < n;i++){
char cc;
scanf("%c",&cc);
str[i]=cc-'0';
}
memcpy(str1,str,sizeof(str));
sort(str,str+n);
int anc[10];
memset(anc,1e6,sizeof(anc));
for(int i=0;i < 10;i++){
bool hk=false;
int key=0;
for(;key < n;key++)
if(str[key] == i){
hk=true;
break;
}
int l,r;
l=r=key;
for(int x=n-1;x >= 0;x--) if(str[x]== i){hk=true;r=x;break;}
if(hk){
anc[i]=0;
while(l >= 0 || r < n){
if(r-l+1 >= k) break;
if( (r+1 < n && l-1 >=0 && str[r+1]-i < i-str[l-1]) || (r+1 < n && l-1 < 0) ){ //每一步都要保证落差足够小。
if(r+1 < n){
r++;
anc[i]+=str[r]-i;
}
}else{
if(l-1 >= 0){
l--;
anc[i]+=i-str[l];
}
}
}
}
}
int mins=1000000,log=-1; //mins为需要改变的数字。
for(int i=0;i < 10;i++){
if( anc[i] < mins) {mins=anc[i];log=i;}
else if(anc[i] == mins){
bool breakout=false;
for(int ij=1;ij < 10;ij++){
for(int j=0;j < n;j++){
if(str1[j] == log+ij) breakout=true;
if(breakout) break;
if(str1[j] == i+ij){log=i;breakout=true;}
if(breakout) break;
}
if(breakout) break;
}
}
}
printf("%d\n",mins);
for(int k=1;;k++){
if(mins <= 0) break;
if(log + k <= 9)
for(int i=0;i < n;i++){
if(str1[i] == log+k){
str1[i]=log;
mins-=k;
if(mins <= 0) goto l1;
}
}
if(log - k >= 0)
for(int i=n-1;i >= 0;i--){
if(str1[i] == log -k){
str1[i]=log;
mins-=k;
if(mins <= 0) goto l1;
}
}
}
l1: for(int i=0;i < n;i++) printf("%d",str1[i]);
printf("\n");
return 0;
}