sk冬赛

我就是我 2022-11-09 12:43 103阅读 0赞

（1）  
**哥俩好数组求解**  
题目描述：  
若两个数字x,y的数位和相同，则x和y是一对“哥俩好数字”。  
要求找到n个不同的正整数，使得这n个数字任意两两之间都是“哥俩好数字”，且数字总和最小。  
n <= 5000

比赛的时候没有估出来，1s内，从1到 1 0 6 10^6 106应该是没问题的。

认为找到的第一个就是最小值，其实不一定。

正解：

#include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    const int maxn=1e6+7;
    using namespace std;
    ll sum[100];
    int cnt[100];
    
    int f(int x)
    { 
        int tot = 0;
        while(x){ 
            tot += x%10;
            x /= 10;
        }
        return tot;
    }
    
    int main()
    { 
        int n;
        cin >> n;
        ll ans = 1e18;
        rep(i, 1, maxn){ 
            int x = f(i);
            if(cnt[x]<n){ 
                cnt[x]++;
                sum[x]+=i;
            }
            if(cnt[x]==n) { 
                ans = min(ans,sum[x]);
            }
        }
        cout << ans;
        
        return 0;
    }
    
     
    
    
    }

（2）  
**神仙采药**  
Description  
您是一个神仙，但您很喜欢采药。

您有一个神奇的背包，背包内有V个格子。

您所在的空间内有一些药，每个药会占用 1或 2 个格子。

每天可以进行一次如下操作：

采摘一个药材放入背包中，若此时背包中没有多余的格子来放入新的药材，可以先将背包中的若干药材扔出去，至于扔多少以及扔几个，全都由您决定。当然您也可以选择不去进行采摘操作。

每一天结束前，神奇背包中的每个药材都会产生一个药丸。

作为神仙，您知道每天您可以采摘的药材类型（即占用格子数目），注意，当天的药材如果不采摘，在第二天就会消失（当天药材仅限当天采摘）。

为了获得尽可能多的药丸，请您计算最终能获得的药丸数目最多是多少？

Input  
给定一个整数 V 表示背包的格子数量，接下来一行一个由1或2构成的字符串 s 表示药占用体积的情况。

其中1表示该药占用体积为 ，2表示该药占用体积为  
V≤100000,∣s∣≤100000

Output  
最多的药丸数目。

Sample Input 1  
3  
212  
Sample Output 1  
5  
Sample Input 2  
5  
12112  
Sample Output 2  
14  
Sample Input 3  
6  
112212  
Sample Output 3  
18  
Sample Input 4  
3  
21121  
Sample Output 4  
10  
Hint  
对于第四组样例：

第一天装入了体积为2的药，该天生产药丸数为1。

第二天装入了体积为1的药，该天生产药丸数为2。

第三天取出了体积为2的药，装入了体积为1的药，该天生产药丸数为2。

第四天未操作，生产药丸数为2。

第五天装入体积为1的药，该天生产药丸数为3

故 1+2+2+2+3=10 个

#include<bits/stdc++.h>
    #define ll long long
    const int maxn=1e6+7;
    using namespace std;
    char str[maxn];
    
    int main()
    { 
        ll v;
        cin >> v >> str;
        ll n = strlen(str);
        ll cnt1=0, cnt2=0;
        ll ans = 0;
        for(ll i = 0; i < n; i++)
        { 
            if(str[i]=='2'){ 
                if(cnt1 + cnt2 * 2 + 2 <= v) cnt2++; //important!
            }
            else{ 
                if(cnt1 + cnt2 * 2 + 1 <= v) cnt1++;
                else if(cnt2>0) cnt1++,cnt2--;
            }
            ans += (cnt1+cnt2);
        }
        cout << ans;
        return 0;
    }

#include<bits/stdc++.h>
    #define ll long long
    #define P pair<ll,ll>
    using namespace std;
    const int maxn=1e6;
    int isprime[maxn],p[maxn];
    vector<int>primes;
    vector<int>vec;
    map<P,P>M;
    ll a,b,cur,prefix_len;
    int getL(int x){ 
        int res=0;
        while(x>0){  res++; x/=10;}
        return res+2;
    }
    inline P get(P p1,P p2,ll len){ 
        return P(p1.first+p2.first,p1.second+p2.second+len*p1.first); 
    }
    P calc(int x,int sum)
    { 
        P p(x,sum);
        if(sum<0) return P(0,0);
        if(M.count(p)) return M[p];
        if(sum==0) return M[p]=P(1,2); //ct,len
        if(primes[x]>sum) return P(0,0);
        return M[p]=get(calc(x+1,sum-primes[x]),calc(x+1,sum),getL(primes[x]));
    }
    void ptchar(char c){ 
        cur++; if(cur>=a&&cur<=b) putchar(c);
    }
    void print(int x){ 
        vector<int>v;
        while(x>0){  v.push_back(x%10); x/=10;}
        for(int i=v.size()-1;i>=0;i--) ptchar(char(v[i]+'0'));
    }
    void print(int x,int sum)
    { 
        if(sum<0||cur>=b) return ;
        if(sum==0){ 
            ptchar('[');
            for(int i=0;i<vec.size();i++){ 
                print(vec[i]);
                if(i==vec.size()-1) ptchar(']');
                ptchar(',');
                ptchar(' ');
            } return ;
        }
        if(primes[x]>sum) return ;
        vec.push_back(primes[x]);
        prefix_len+=getL(primes[x]);
        ll len=prefix_len*calc(x+1,sum-primes[x]).first+calc(x+1,sum-primes[x]).second;
        if(len+cur>=a) print(x+1,sum-primes[x]);
        else cur+=len;
        
        vec.pop_back();
        prefix_len-=getL(primes[x]);
        len=prefix_len*calc(x+1,sum).first+calc(x+1,sum).second;
        if(len+cur>=a) print(x+1,sum);
        else cur+=len;
    } 
    int main()
    { 
        isprime[1]=false;
        fill(isprime,isprime+maxn,true);
        for(int i=2;i<maxn;i++){ 
            if(isprime[i]){ 
                primes.push_back(i);
                for(int j=i+i;j<maxn;j+=i) isprime[j]=false;
            }
        }
        scanf("%lld%lld",&a,&b);
        for(int i=2;i<100000&&cur<b;i++){  //试探过，i最大到2096，这个范围的素数也就300来个，所以记忆化 
            ll len=calc(0,i).second;
            if(cur+len>=a) print(0,i);
            else cur+=len;
        }
        puts("");
        return 0;
    }

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    using namespace std;
    vector <string> word;//存放单词和符号
    
    bool bigletter(char c){ //判断是不是大写字母
    	if(c>='A'&&c<='Z') return true;
    	return false;
    }
    bool smallletter(char c){ //判断是不是小写字母
    	if (c>='a'&&c<='z') return true;
    	return false;
    }
    
    bool bigletterword(string s){ //判断是不是只有首字母大写
    	if (!bigletter(s[0])) return false;//首不是大写
    	if (s.size()<=1) return false;//长度大于1
    	for (int i=1;i<s.size();i++){ //只能有一个大写
    		if (!smallletter(s[i])) return false;
    	}
    	return true;// 否则合格
    }
    
    void work(){ //处理每一个单词或符号
    	int n=word.size();
    	for (int i=0;i<n;i++){ 
    		int inow=i;
    		if (!bigletterword(word[i]))//如果不需要缩写则直接输出
    			cout<<word[i];
    		if (bigletterword(word[i])) { 
    			if (i!=n-1){ //最后一位要么跟着前面的缩写，要么就是只有一个符合的所以不用缩写
    				if (word[i+1]==" "&&bigletterword(word[i+2])){ 
    					int j;
    					for (j=i;j<n;j++){ 
    						if ((j-i)%2==0){ 
    							if (!bigletterword(word[j])){ 
    								j--; 
    								break;
    							}
    								
    							else cout<<word[j][0];
    						}
    						else if (word[j]!=" ") break;
    						
    					}//j停在了最后符合要求的word的最后一位的后面一位
    					cout<<" (";
    					for (int k=i;k<j-1;k+=2)
    						cout<<word[k]<<' ';
    					cout<<word[j-1]<<')';
    					inow=j-1;//i直接跳过缩写的部分
    				}
    				else cout<<word[i];
    			}
    			else cout<<word[i];
    		}
    		i=inow;
    	}
    } 
    
    int main(){ 
    	string s;
    	while(getline(cin,s)){ 
    		if (s.size()==0) break;//如果输入为空就停止
    		string w="";//存放单词
    		for (int i=0;i<s.size();i++){ //循环s
    			if (bigletter(s[i])||smallletter(s[i])) w+=s[i];//如果是字母则直接压到s里
    			if (!bigletter(s[i])&&!smallletter(s[i])){ //否则把单词压到word了，并把符号也压进去
    				word.push_back(w);
    				w="";
    				w+=s[i];
    				word.push_back(w);
    				w="";
    			}
    		}
    		word.push_back(w);//把最后一个单词压进去
    		work();
    		word.clear();//清空word
    		cout<<endl;
    	}
    	return 0;//完美结束
    }