AcWing第 79 场周赛

AcWing 4722. 数列元素

模拟即可

int n;
const int N=510;
int a[N];
void solve()
{
	cin>>n;
	rep(i,1,n)
	{
		int s=0;
		rep(j,1,i)s+=j;
		if(s==n)
		{
			YES;
			return;
		}
	}
	NO;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4723. 队列

数学+二分

int n;
const int N=33;
int a[N],s[N];
void solve()
{
	cin>>n;
	a[1]=5;
	rep(i,2,N-1)a[i]=a[i-1]*2;
	rep(i,1,N)s[i]=s[i-1]+a[i];
	int l=1,r=N-1;
    map<int,char>mp;
    mp[1]='a',mp[2]='b',mp[3]='c',mp[4]='d',mp[5]='e';
	while(l<r)
	{
		int mid=l+r>>1;
		if(s[mid]>=n)r=mid;
		else l=mid+1;
	}
	int sum=a[r];//该周期个数 ;
	int now=n-s[r-1];//该周期的第几个
	int cnt=a[r]/5;
	now=ceil(now*1.0/cnt)*cnt;
	int x=0;
	int h=0;
	while(x<=now)
	{
		h++;
		x+=cnt;
	}
	cout<<mp[--h]<<endl;
}
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

4724. 靓号

模拟+贪心。
花费最小并且字典序最小，分类讨论：

1. 花费不同，按照花费最小进行从小到大排序
2. 否则，如果可从小变大也可从大变小，则从大数变成小数
3. 否则，如果都是从小变大，那么倒叙，否则正序

/*
    悲观看待成功，乐观看待失败。 
    author：leimingze 
*/
#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此 
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int n,k;
string s;
void solve()
{
	cin>>n>>k;
	cin>>s;
	string str=s;
	string res=s;
	int minv=ll_INF;
	vector<PII>v;
	rep(i,0,n-1)v.pb({i,s[i]-'0'});
	rep(i,0,9)
	{
		s=str;
		sort(all(v),[&](PII &a,PII &b){
			if(abs(i-a.y)!=abs(i-b.y))return abs(i-a.y)<abs(i-b.y);
			else
			{
				if(i-a.y!=i-b.y)return i-a.y<i-b.y;
				else if(i-a.y>0)return a.x>b.x;
				else return a.x<b.x;
			}	
		});
		int sum=0;
		for(int j=0;j<min((int)v.size(),k);j++)
			sum+=abs(v[j].y-i),s[v[j].x]=i+'0';
		if(minv>sum)
			minv=sum,res=s;
		else if(minv==sum)
			if(res>s)res=s;
	}
	cout<<minv<<endl;
	cout<<res<<endl;
}
signed main() 
{
	io;
	int _;_=1;
	//cin>>_;
	while(_--)solve();                                                                                                                                       
	return 0;
}
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