Codeworks round 739 (Div. 3) problem solving Report

A

The question ： Find out the k One is neither 3 The multiples of are not expressed in 3 Ending number
Ideas ：$1\le t\le 100,1\le k\le 1000$ From the example $k=1000$ when , The answer is $1666$, So violence enumerates $1\sim 1666$ that will do

#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

The question ： An even number of people form a circle by number , Give the number of two relative positions a,b, Seek number c Number of the opposite person
Ideas It is not difficult to think of or observe the number difference between two relative positions 1 That's half the population .c Add half of the number of people to the total number of people, and then take the mold . If the number is greater than the calculated total number, it means that it does not exist .

#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

The question ： Fill in the numbers as shown , Ask for numbers $k$ The location of
Ideas ： Easy to get every time you write to the first column , What you write must be the square of some number , So we can quickly get the result by opening the root , The current number is the number of layers , At the same time, we can observe that in the $x$ The number of left columns and bottom rows of the layer is $x$,（ Pay attention to the last instance of the current layer ）.

#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

The question ： Give a number $n$, You can delete one of it , You can also add a digit after it , Change this number to $2$ A power of （ Prefixed with zero does not count $2$ Power of power ）, Minimum number of operations .
Ideas ： Consider that deleting and adding operations are important for 2 Hexadecimal representation has no obvious characteristics , So we think about this problem in the form of string . Make n The length of is len( obviously $len\le 9$), For any string, we can be in len+1 Turn it into 2 Power of power （ That is to say, delete all , Add one digit 2 Power of power ） So the length of the final string must not exceed 18, stay $longlong$ Within the scope of .($2^{60}>1e18$)
So let's enumerate 2 Of 0~60 Power to match greedy violence , Meet and... From left to right 2 The same power of is retained , Otherwise delete . Finally, add the remaining number . stay $60$ The lowest of the species .

#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

The question ： Give you a string s, Every time I put a string s Copy to string t Back (t Initially empty ), And then in s Select a character from , Delete all this character ;
Repeat the above two operations , Until the string s It's empty . Here you are. t character string , Ask you to restore s strand , And find its deletion sequence .
Ideas ： Consider every delete , The number of character sets is reduced by one , If from the string t Looking forward from the back of , You can find , The character set is growing ;
Easy to think of , character a stay t Is the number of times =a stay s Is the number of times *a Time to live .
stay t The number of occurrences in can be traversed t obtain , Survival time can be transformed into （ Total character set size - The first few letters from the back to the front ）.（ On the way from back to front , We can work out the order of character deletion ）, So we got it s The number of characters in the string , That is to get s strand . But there is still an impossible situation , Just use s A series of violence to simulate the process , Take a look and t If the string and match do not match .

#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

The question ： Give a number $n$($n$<=1e9), You ask for the smallest $x$, Satisfy $x$>=$n$, also $x$ The total number of digits used in the decimal representation <=$k$(1<=$k$<=10)
Ideas ：

1. First , as everyone knows , If $n$ The numbers used in <=$k$, So we're going to export $n$ that will do .
2. If n The number in is greater than $k$, So let's take n In the high order of $k-1$ A digital （ Greedy thoughts , The higher the , The less you want it to change ）, And then take the enumeration No $k$ What is a number . With this k A digital , How to find the smallest $x$, Satisfy $x$>=$n$ Well . Similarly, we greedily match , For the same person , If we can get and n The same number , Let's take this number first ; And once a certain digit is compared to n The big one , Then the next position , We greedily choose the small one .
3. The point is , This greed has an operation of repentance , Suppose we now match to pos Yes. , stay pos Bit before ,n and x Are all the same , But in pos position , None of our numbers is greater than n This one , Let's go back to the previous position , Make the nearest one bigger . The next digits can be greedily selected .
4. Such as : n=1092,m=2, Suppose our current character set is {0,1}, We can both greedily choose the first two 10XX; In third place , No matter what you choose, you can't make $x$>=$n$; This time we will return to the second place , Give Way x The second place becomes bigger 1, Then the next bit can be greedily selected 0 了 , The final answer is 1100;

ops:
There are many special judgments , It's ugly ;
Time complexity is about 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;
}