文章目錄
- A
- B
- C
- D
- E
- F1
- F2
A
題意：找出第k個既不是3的倍數也不以3結尾的數
思路：
1
≤
t
≤
100
,
1
≤
k
≤
1000
1\le t\le100,1\le k\le1000
1≤t≤100,1≤k≤1000由樣例得
k
=
1000
k=1000
k=1000時，答案等于
1666
1666
1666,所以暴力列舉
1
～
1666
1\sim1666
1～1666即可
#include<bits/stdc++.h>
using namespace std;
int ans[1010], now;
bool pan(int x) {
if (x % 3 == 0 || x % 10 == 3)return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for (int i = 1; i <= 1666; ++i) {
if (pan(i))
ans[++now] = i;
}
int _; cin >> _; while (_--) {
int x; cin >> x;
cout << ans[x] << '\n';
}
}
B
題意：偶數個人按編號圍成一個圈，給出兩個相對的位置的編號a,b，求編號c相對的人的編號
思路不難想到或觀察到兩個相對位置之間的編號差加1即為一半的人數，c的編號加一半的人數再對總人數取模即可，編號大于計算出的總人數即為不存在，
#include<bits/stdc++.h>
using namespace std;
int ans[1010], now;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int _; cin >> _; while (_--) {
int a, b, c; cin >> a >> b >> c;
int n = abs(a - b);
if (a > 2 * n || b > 2 * n || c > 2 * n)cout << "-1\n";
else cout << (c + n - 1) % (2 * n) + 1 << '\n';
}
}
C
題意：按照圖示填補數字，問數字
k
k
k的位置
思路：容易得到每次寫到第一列時，所寫的一定是某個數的平方，所以我們可以通過開根號的方法來快速得到，當前數是在第幾層的第幾個，同時我們可以觀察得出在第
x
x
x層的左列和底行的個數為
x
x
x，（注意特判當前層最后一個的情況），
#include<bits/stdc++.h>
using namespace std;
int ans[1010], now;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _; cin >> _; while (_--) {
int k; cin >> k;
int c = sqrt(k);
k -= c * c;
c++;
if (k == 0)cout << c - 1 << ' ' << 1 << '\n';
else if (k <= c)cout << k << ' ' << c << '\n';
else cout << c << ' ' << 2 * c - k << '\n';
}
}
D
題意：給定一個數
n
n
n,你可以洗掉它的某一位，也可以在它后面加上一位，使這個數變為
2
2
2的某次冪（有前綴零不算
2
2
2的次冪），問最小操作次數，
思路：考慮到洗掉和添加的操作對于2進制表示并沒有什么明顯的特性，所以我們以字串的方式來思考這到題，令n的長度為len(顯然
l
e
n
≤
9
len\le9
len≤9)，對于任意串我們都能在len+1次將其變為2的次冪（即全刪完，加一個一位的2的次冪）所以最終串的長度一定不超過18,在
l
o
n
g
l
o
n
g
long long
longlong的范圍之內，(
2
60
>
1
e
18
2^{60}>1e18
260>1e18)
所以我們列舉2的0~60次冪進行貪心的暴力匹配，從左至右遇到和2的次冪一樣的就保留，否則洗掉，最后添加剩下的數，在
60
60
60種中取最小值，
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll way[70][20];
ll len[70];
ll num[70];
char s[15];
ll n;
ll ans;
void fen(ll i) {
ll x = 1ll << i;
ll ans[20] = { 0 }, now = 19;
while (x) {
ans[now--] = x % 10;
x /= 10;
}
len[i] = 19 - now;
memcpy(way[i], ans + now + 1, len[i] * sizeof(ll));
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for (ll i = 0; i <= 60; ++i)fen(i);
int _; cin >> _; while (_--) {
memset(num, 0, sizeof num);
cin >> s;
for (n = 0; s[n]; ++n) {
for (int i = 0; i <= 60; ++i) {
if (num[i] < len[i] && way[i][num[i]] == s[n] - '0')
num[i]++;
}
}
ans = 100;
for (int i = 0; i <= 60; ++i) {
ans = min(ans, n + len[i] - 2 * num[i]);
}
cout << ans << '\n';
}
}
E
題意：給你一個字串s，每次會把串s復制到串t后面(t初始為空)，然后在s中選擇一個字符，將所有這個字符都洗掉；
重復上面兩個操作，直到串s為空，給你t字串，要求你還原s串，并且找到它的洗掉序列，
思路：考慮到每次洗掉，字符集數量就減一，如果從串t的后面往前看，可以發現，字符集是不斷變大的；
容易想到，字符a在t中出現的次數=a在s中出現的次數*a存活的時間，
在t中出現的次數可以遍歷t得到，存活的時間可以轉化成 （ 總的字符集大小 - 從后往前第幾個出現的字母），（在從后往前遍歷的途中，我們開可以處理出字符洗掉的次序），那么就得到了s串中各字符的數量，也就是得到了s串，但是題目還存在不可能的情況，就用s串暴力模擬一下程序，看一下和t串匹不匹配即可，
#include<bits/stdc++.h>
#define N 10005
using namespace std;
int t;
char s[500050];
int cnt[30];
int p[30];
int num=0;
char a[500050],b[500060];
vector<char>v;
int main(){
cin>>t;
while(t--){
scanf("%s",s);
int len=strlen(s);
num=0;
for(int i=0;i<26;i++)cnt[i]=0,p[i]=0;
for(int i=0;i<len;i++){
cnt[s[i]-'a']++;
}
for(int i=0;i<26;i++)if(cnt[i])num++;
int f=1;
v.clear();
for(int i=len-1;i>=0;i--){
if(!p[s[i]-'a']){
v.push_back(s[i]);
p[s[i]-'a']=cnt[s[i]-'a']/num;
if(cnt[s[i]-'a']%num!=0){
f=0;break;
}
num--;
}
}
int tot=0;
for(int i=0;i<26;i++)tot+=p[i];
int pos=0;
for(int i=0;i<len;i++){
if(p[s[i]-'a']){
p[s[i]-'a']--;tot--;
}else {
f=0;break;
}
if(tot==0){
pos=i;break;
}
}
int cnt=0;
int c1=1,c2=v.size();
if(f){
for(int i=0;i<=pos;i++)if(s[i]!=v[c2-c1])a[++cnt]=s[i];
for(int i=pos+1;i<len;i++){
for(int j=1;j<=cnt;j++){
if(s[i]!=a[j]){
f=0;break;
}else i++;
}
if(!f)break;
int res=0;
c1++;
for(int j=1;j<=cnt;j++){
if(a[j]!=v[c2-c1])b[++res]=a[j];
}
for(int j=1;j<=res;j++)a[j]=b[j];
cnt=res;
i--;
}
}
if(tot!=0||!f)cout<<-1;
else {
for(int i=0;i<=pos;i++)cout<<s[i];
cout<<" ";
for(int i=v.size()-1;i>=0;i--)cout<<v[i];
}
cout<<endl;
}
}
F1
F2
題意：給定一個數
n
n
n(
n
n
n<=1e9),你要求出最小的
x
x
x,滿足
x
x
x>=
n
n
n,并且
x
x
x在十進制表示下用到的數字總數<=
k
k
k(1<=
k
k
k<=10)
思路：
- 首先，眾所周知，如果 n n n中用到的數字<= k k k，那么我們直接輸出 n n n即可，
- 如果n中的數字大于 k k k，那么我們取n的高位中的前 k ? 1 k-1 k?1個數字（貪心思想，越高位，越不希望它改變），然后再取列舉第 k k k個數字是什么即可，有了這k個數字，怎么去求最小的 x x x,滿足 x x x>= n n n呢，同樣我們貪心地取匹配，對于同一位，如果我們能取到和n一樣地數字，我們先取這個數字；而一旦某一位取地數字比n那一位大，那么接下來地位，我們貪心地選取小的即可，
- 重點在于，這個貪心有一個反悔的操作，假設我們現在匹配到pos位了，在pos位之前，n和x都一樣，但是在pos位，我們的數字集合中沒有一個大于n的這一位，我們就回到前面的位中，把最近的能變大的一位變得更大，之后的位數就能貪心地選取了，
- 如: n=1092,m=2，假設我們當前的字符集是{0，1},前兩位我們都能貪心地選取得到10XX;到第三位的時候，不管選什么都不能令 x x x>= n n n；這個時候我們就回到第二位，讓x的第二位變成更大的1，那么接下來的位就可以貪心地選0了，最后答案就是1100；
ops:
特判比較多，寫的比較丑；
時間復雜度大概是O（T * 10 * 10 * 10）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,t;
ll b[1004];
ll a[1040];
int vis[14];
int main(){
cin>>t;
while(t--){
cin>>n>>m;
int len=0;
for(int i=0;i<10;i++)vis[i]=0;
while(n){
a[++len]=n%10;
n/=10;
}
int num=0;
for(int i=len;i>=1;i--){
if(!vis[a[i]]){
vis[a[i]]=1;num++;
}
}
if(num<=m){
for(int i=len;i>=1;i--){
cout<<a[i];
}
cout<<endl;
continue;
}
num=0;
int pos=0;
for(int i=0;i<10;i++)vis[i]=0;
for(int i=len;i>=1;i--){
if(num==m-1){
pos=i;break;
}
if(!vis[a[i]]){
vis[a[i]]=1;num++;
}
}
ll ans=1e13;
for(int i=len;i>=pos+1;i--){
b[i]=a[i];
}
for(int j=0;j<=9;j++){
if(vis[j])continue;
vis[j]=1;
int f=0;
int ff=0,flag=0;
for(int i=pos;i>=1;i--){
if(!f){
ff=0;
for(ll k=a[i];k<=9;k++){
if(vis[k]){
ff=1,b[i]=k;break;
}
}
if(!ff){
if(!flag){
if(i<pos){
while(i<pos){
i++;
for(ll k=a[i]+1;k<=9;k++){
if(vis[k]){
ff=1;b[i]=k;
break;
}
}
if(ff)break;
}
}
flag=1;
}else break;
if(!ff)break;
}
}else {
for(ll k=0;k<=9;k++){
if(vis[k]){
b[i]=k;break;
}
}
}
if(b[i]>a[i])f=1;
}
if(ff){
ll res=0;
for(ll k=len;k>=1;k--)res=res*10+b[k];
ans=min(ans,res);
}
vis[j]=0;
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/295223.html
標籤：其他
上一篇：【C語言初階】一次性搞定分支陳述句和回圈陳述句（干活滿滿+建議收藏）
下一篇：const char *str，char const *str，char *const str的區別，及const詳解