A:给定两正整数 n,k,从 1 到 n 中选取最多的不相同的数使得这些数构成的集合不存在元素之和为 k 的子集。
思路:大于k的肯定可以,然后判断一下剩余小于k的个数是奇数还是偶数
while(t--) { int n, k; cin >> n >> k; vector<int> v; for(int i=k+1;i<=n;i++) v.push_back(i); int tmp=k-1; if(tmp%2) { int cnt=ceil(1.0*tmp/2); while(cnt) { v.push_back(tmp); tmp--; cnt--; } } else { int cnt=tmp/2; while(cnt) { v.push_back(tmp); tmp--; cnt--; } } if(v.empty()) cout << 0 << endl; else { cout << v.size() << endl; for(auto i : v) cout << i << " "; cout << endl; } }
B:
题意:给你一个时间,通过镜子显示出来的时间要是合理的,问最快一次让镜子里的时间是多少
思路:合理的数字只有0 1 2 5 8。依次往下判断当前时间是否合理即可
代码:
#include <bits/stdc++.h> #include <iostream> #include <cstring> #include <algorithm> #include <set> typedef long long ll; using namespace std; const int N = 1e5+5; int l[N],r[N];int h,m; int hh,mm; int a[10]={0,1,5,-1,-1,2,-1,-1,8,-1}; int judge(int x,int y) { if(a[x%10]==-1||a[x/10]==-1||a[y%10]==-1||a[y/10]==-1) { return 0; } if(a[y%10]*10+a[y/10]<h&&a[x%10]*10+a[x/10]<m) return 1; return 0; } int main() { int t; cin >> t; while(t--) { char c; cin >> h >> m; cin >> hh >> c >> mm; while(judge(hh,mm)==0) { mm=(mm+1)%m; if(mm==0) hh = (hh+1)%h; } cout << hh/10 << hh%10 << ":" << mm/10 << mm%10 << endl; } return 0; }C:
题意:给你一个字符串s,输出一个新的字符串p,且新字符串中出现的字符要是字符串s里的,且每种新字符个数要是k的整数倍,输出满足此条件字符串,且字符串p大于等于字符串s,同时字典序最小。
思路:首先,n不是k的整数倍,输出-1,然后枚举字符串s中每种字符出现的个数并算出每种字符差多少个(sum)可变成k的倍数,如果sum等于0,直接输出s。要保证字符串p大于等于字符串s,同时字典序最小,我们只需要倒序枚举字符串s,当前位置i上的字符修改后(修改的肯定是大于当前字符),统计此时还差多少个字符可变成k的整数倍,如果此时能修改成满足题意的字符串p,则输出,否则继续枚举,具体分析看代码与注释。
代码:
while(t--) { memset(a,0,sizeof(a)); int n,k; cin >> n >> k; scanf("%s",s+1); if(n%k) { cout << "-1" << endl; continue; } int sum=0; for(int i=1;i<=n;i++) { a[s[i]-'a']++;//统计每个字母有多少个 } for(int i=0;i<26;i++) { sum+=(k-a[i]%k)%k;//统计每个字符差几个可为k的倍数 } if(sum==0) { cout << s+1 << endl; continue; } int flag=0; for(int i=n;i>0;i--)//倒叙枚举字符串s { if(flag) break; sum-=(k-a[s[i]-'a']%k)%k; a[s[i]-'a']--; sum+=(k-a[s[i]-'a']%k)%k; for(int j=s[i]-'a'+1;j<=25;j++)//枚举第i位上修改后的字符 { if(flag) break; int cur = sum;//当前还差cur个字符可变成任意字符 cur-=(k-a[j]%k)%k;//减去修改前该字母的影响 a[j]++;//修改后的字母个数+1 cur+=(k-a[j]%k)%k;//加上修改后该字母对cur的影响 a[j]--;//还原,用于下次查找 if(cur<=n-i)//n-i代表可修改的个数,cur代表当前还需要修改个数,所有当可修改数大于需要数,即可使修改后的字符串满足题意 { int x=i,y=j; memset(a,0,sizeof(a)); s[x]=y+'a';//修改当前字符s for(int i=1;i<=x;i++) a[s[i]-'a']++;//统计前x个没改变的字符个数 int sum=n-x;//可修改的个数 for(int i=0;i<=25;i++) sum-=(k-a[i]%k)%k;//多余的空位用a补全,因为总长和其余每种字符数量都可以被k整除,所以填入a后a的数量也满足要求 for(int i=1;i<=x;i++) putchar(s[i]);//前x个字符是没有改变 for(int i=1;i<=sum;i++) putchar('a');//多余的位置补a,满足题意 for(int i=0;i<=25;i++) for(int j=1;j<=(k-a[i]%k)%k;j++) putchar('a'+i);//该字符还需输出的数量 putchar('\n'); flag=1; break; } } } }