multi多校-1

自用笔记算法

muti多校-1

HDU 6033

题目要求

找出小于等于2^m次方的最大的10^x次方的数 输出x

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int flag=1;
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int m;
    while(cin>>m){
        cout<<"Case #"<<flag++<<": ";
        cout<<(int)(m*log(2)/log(10))<<endl;
    }
    return 0;
}

思路

解对数不等式1<=2^m/10^x<10 解得x=(int)(m*ln(2)/ln(10))

HDU 6034

题目要求

最大映射
给出若干个字符串 期中a-z可以有数字0-25替换 且一一对应 每一个字符串不能含有前导0 并且满足至少有一个字母不出现在首位
替换后每个字符串当成26进制数处理 求最大和

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int flag=1;
struct node{
    int t[maxn];
}a[30];
int vis[30],k[30];
int cmp(int x,int y){
    if(a[x].t[0]>a[y].t[0]) return 1;
    if(a[x].t[0]<a[y].t[0]) return 0;
    for(int i=a[x].t[0];i>=1;i--){
        if(a[x].t[i]>a[y].t[i]) return 1;
        if(a[x].t[i]<a[y].t[i]) return 0;
    }
    return 0;
} 
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    while(cin>>n){
        cout<<"Case #"<<flag++<<": ";
        mm(vis,0);
        for(int i=0;i<=25;i++) mm(a[i].t,0);
        for(int i=0;i<=25;i++) k[i]=i;
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            vis[s[0]-'a']=1;
            int len=s.length();
            for(int j=0;j<len;j++){
                a[s[j]-'a'].t[len-j]++;
                a[s[j]-'a'].t[0]=max(a[s[j]-'a'].t[0],len-j);
            }
        }
        int maxlen=0;
        for(int i=0;i<=25;i++){
            for(int j=1;j<=a[i].t[0];j++){
                a[i].t[j+1]+=a[i].t[j]/26;
                a[i].t[j]%=26;
            }
            while(a[i].t[a[i].t[0]+1]>0){
                a[i].t[0]++;
                a[i].t[a[i].t[0]+1]+=a[i].t[a[i].t[0]]/26;
                a[i].t[a[i].t[0]]%=26;
            }
            maxlen=max(maxlen,a[i].t[0]);
        }
        sort(k,k+26,cmp);
        LL ans=0;
        int now=25;
        while(vis[k[now]] && now>0) now--;
        for(int i=now;i<=25;i++) k[i]=k[i+1];
        LL base=1;
        for(int i=1;i<=maxlen;i++){
            for(int j=0;j<25;j++){
                ans=(ans+(LL)(25-j)*base*a[k[j]].t[i])%mod;
                ans%=mod; 
            }
            base=(base*26)%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路

node a数组表示对于26个字母 对应的权值 t[0]存放该字母权重的长度 t[1]开始存放权重
开始对于每个字符串 从首位开始遍历 对应len-j的位置++
再对t[1]开始的权重进行转换进制操作 转换成26进制 注意可能在原来t[0]的长度上溢出 实时维护t[0]的长度并且找出maxnlen
数组k表示对26个字母的映射 对数组k排序 cmp针对权重比较
对于前导0的处理：从25开始从尾部遍历 找到第一个未在开头出现(vis数组判断)并且出现次数最小的位置 令该位置为0 把后面的数字
全部左移一位 由于最后一位是0不影响结果所以无需把该位置移到最后
对于1-maxlen 遍历每个位置 对于每个位置遍历0-24(25位置是0无需考虑) 利用k[j]找到从大到小权重对应的字母 用替换的数字基数base该位置大小即可
注意取模操作

HDU 6043

题目要求

Q有n双袜子 每双袜子对应1-n的一个编号且唯一
每天早上Q穿上编号最小的数字 每天晚上脱下 并且把袜子放入篮子里
篮子里的袜子如果等于n-1 Q会把这些袜子洗掉 在第二天的傍晚放回衣柜
问第k天早上穿上袜子的编号是多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int flag=1;
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    LL n,k;
    while(cin>>n>>k){
        cout<<"Case #"<<flag++<<": ";
        LL re;
        if(n>=k) re=k;
        else{
            LL temp=k-n;
            LL ans=(temp-1)/(n-1);
            if(ans&1){
                re=(temp-1)%(n-1)+1;
                if(re==n-1) re=n;
            }
            else re=(temp-1)%(n-1)+1;
        }
        cout<<re<<endl;
    }
    return 0;
}

思路

用优先队列模拟后打表找规律
发现规律
(n==4)
1234 123 124 123 124···
(n==5)
12345 1234 1235 1234 1235···
若k<=n直接输出
否则减去前n项后 (k-1)/(n-1)找出循环次数
为奇为偶额外判断 若为奇数需特判ans==n-1的情况 此时ans=n

本文标题:multi多校-1

文章作者:Hippopmonkey

发布时间:2017-07-26, 00:07:54

最后更新:2017-07-26, 00:31:17

原始链接:http://xuboming8.github.io/2017/07/26/multi多校-1/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. muti多校-1
    1. 1.1. HDU 6033
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6034
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6043
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|