2026小码王自招辅导Day02-模拟

userId_undefined
深圳-禹云龙

2026-06-30 23:33:00

发布于：广东

2阅读
0回复
0点赞

比赛

防护伞

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
const double PI=3.1415926535;
int x[N],y[N];
int dis(int a,int b,int c,int d){
    return (a-c)*(a-c)+(b-d)*(b-d); 
}
void solve(){
	int ans=1e9; 
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>x[i]>>y[i];
	}
    for(int i=1;i<=n;i++){
        int res=0;
        for(int j=1;j<=n;j++){
            res=max(res,dis(x[i],y[i],x[j],y[j])); 
        }
        ans=min(ans,res); 
    }
    cout<<fixed<<setprecision(4)<<(double)ans*PI<<"\n";
    return;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--){
        solve();
    }
}
  • 思路整理：找到最小的一个伞的半径，使得该伞在以某个黑子为伞的圆心时可以覆盖到其他所有的黑子，那么要想使的伞半径最小肯定是刚好某个点位于伞的边缘上，因为不能浪费材料。所以这个半径一定是在任意两个点之间的距离中选出的。
  • 解题思路：枚举圆心，那么此时半径就是圆心到距离该圆心最远的那个点之间的距离，在这个枚举的过程中找到最小半径，时间复杂度是O(n2)O(n^{2})。

图像压缩

#include<bits/stdc++.h>
#define int long long 
using namespace std;
typedef pair<int,int>PII;
typedef pair<PII,int>PPI;
const int N=1e5+5;
const int mod=1e6+7;
string s[N];
vector<string>g;
map<string,int>mp;
map<int,string>mp1;
int m;
struct str{
	string s;
	int cnt;
}E[N];
bool cmp(str a,str b){
	if(a.cnt!=b.cnt)return a.cnt>b.cnt;
    return a.s<b.s;
}
void init(){
	int id=0; 
	for(auto v:mp){
		E[++m]={v.first,v.second};
	}
	sort(E+1,E+1+m,cmp);
	for(int i=1;i<=16;i++){
		cout<<E[i].s;
		g.push_back(E[i].s);
	}
	cout<<"\n";
}
int To10(string s){
	int num=0;
	for(int i=0;i<2;i++){
		int d=s[i]-'0';
		if(s[i]>='A') d=s[i]-'A'+10;
		num=num*16+d;
	}
	return num;
}
int get(string s){
	int mi=1e18,id=-1;
	for(int i=0;i<16;i++){
		int val=abs(To10(s)-To10(g[i]));
		if(mi>val){
			mi=val;
			id=i;
		}
	}
	return id;
}
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=" "+s[i];
		for(int j=1;j<s[i].size();j+=2){
			string s2=s[i].substr(j,2);
			mp[s2]++;
		}
	}
	init();
	for(int i=1;i<=n;i++){
		for(int j=1;j<s[i].size();j+=2){
			string s1=s[i].substr(j,2);
			int d=get(s1);
			if(d<=9) cout<<d;
			else {
				char c='A'+d-10;
				cout<<c;
			}
		}
		cout<<"\n";
	}
}
signed main(){
//	cout<<To10("FF");
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _=1;
//	cin>>_;	
	while(_--){
		solve();
	}
}
  • 思路整理：256级灰阶中每个像素点是以16进制形式给出，我们要找出出现次数前16像素点，进行编号，其他像素点需要根据距离来映射到前16个像素点的某一个，最后将原来256级的灰阶按照编号转为16级灰阶
  • 解题思路：map统计出现次数，结构体排序，排出前16像素点，后续转化阶段就暴力找与之匹配的像素点并输出其对应的16进制即可；

二进制

#include <bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<pair<int,int>,int> PPI;
typedef pair<int,pair<int,int>> PIP;
typedef pair<int,int>PII;
const int N = 1e7 + 5;
const int M=1e9+7;
const int M1=1000003;
int a[N];
void solve(){
	int n,m;
	string s,op;
	cin>>n>>m;
	cin>>s>>op;
	s=" "+s;
	op=" "+op;
	for(int i=1;i<=n;i++)a[i]=s[i]-'0';
	int id=n;
	for(int i=1;i<=m;i++){
		if(op[i]=='*')a[++id]=0;
		else if(op[i]=='+')a[id]++;
		else if(op[i]=='-')a[id]--;
		else{
			if(a[id]>=0) a[id-1]+=a[id]/2;
			else a[id-1]+=(a[id]-1)/2;
			id--;
		}
	}
	for(int i=id;i>=1;i--){
		if(a[i]>=0) {
			a[i-1]+=a[i]/2;
			a[i]=a[i]%2;
			
		}
		else {
			a[i-1]+=(a[i]-1)/2;
			a[i]=(a[i]%2+2)%2;
		}
	}
	for(int i=1;i<=id;i++) cout<<a[i];
	return ;
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

思路整理：在二进制下*和/分别对应左移和右移，+1和-1则是在对应位上进行累加，那么使用延迟标记的思想，当除时再去推标记，最后结束后做最后的进位操作

三角魔方

#include <bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<pair<int,int>,int> PPI;
typedef pair<int,pair<int,int>> PIP;
typedef pair<int,int>PII;
const int N =2e3 + 5;
const int M=1e9+7;
const int M1=1000003;
char ch[20] = {' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'};
char a[20],ans[20];
string s;
int a1,b1;
void u3() {
	swap(a[5], a[11]); swap(a[11], a[12]);
}
void u5() {
	swap(a[2], a[6]); swap(a[6], a[7]); swap(a[7], a[13]); swap(a[13], a[14]);
}
void u7() {
	swap(a[1], a[3]); swap(a[3], a[4]); swap(a[4], a[8]); swap(a[8], a[9]); swap(a[9], a[15]); swap(a[15], a[16]);
}
void r3() {
	swap(a[3], a[4]); swap(a[2], a[3]);
}
void r5() {
	swap(a[8], a[9]); swap(a[7], a[8]); swap(a[6], a[7]); swap(a[5], a[6]);
}
void r7() {
	swap(a[15], a[16]); swap(a[14], a[15]); swap(a[13], a[14]); swap(a[12], a[13]); swap(a[11], a[12]); swap(a[10], a[11]);
}
void d3() {
	swap(a[14], a[15]); swap(a[9], a[15]);
}
void d5() {
	swap(a[12], a[13]); swap(a[7], a[13]); swap(a[7], a[8]); swap(a[4], a[8]);
}
void d7() {
	swap(a[10], a[11]); swap(a[5], a[11]); swap(a[5], a[6]); swap(a[2], a[6]); swap(a[2], a[3]); swap(a[1], a[3]);
}
void init(){
	for(int i=1;i<=16;i++){
		a[i]=ch[i];
	}
}
void rotate() {
	for (int i=0; i<(int)s.size(); i+=2) {
		if (s[i]=='U') {
			if (s[i+1]=='3') u3();
			else if (s[i+1]=='5') u5();
			else if (s[i+1]=='7') u7();
		}
		else if (s[i]=='R') {
			if (s[i+1]=='3') r3();
			else if (s[i+1]=='5') r5();
			else if (s[i+1]=='7') r7();
		}
		else if (s[i]=='D') {
			if (s[i+1]=='3') d3();
			else if (s[i+1]=='5') d5();
			else if (s[i+1]=='7') d7();
		}
	}
}
int qpow(int a,int b,int mod){
	int ans=1;
	while(b!=0){
		if(b%2==1)ans=ans*a%mod;
		b=b>>1;
		a=a*a%mod;
	}
	return ans%mod;
}
int getIndex(char c){
	for(int i=1;i<=16;i++){
		if(a[i]==c)return i;
	}
}
int getEnd(char c){
	int cnt=0;
	map<int,int>mp;
	int cy=-1;
	while(1){
		rotate();
		cnt++;
		int id=getIndex(c);
		if(mp[id]!=0){
			cy=cnt-mp[id];
			break;
		}
		mp[id]=cnt;
	}
	int k=qpow(a1,b1,cy);
	k=((k-cnt)%cy+cy)%cy;
	while(k--){
		rotate();
	}
	return getIndex(c);
}
void solve(){
	cin>>s;
	cin>>a1>>b1;
	init();
	int an=1;
	for(int i=1;i<=b1;i++) {
		an*=a1;
		if(an>100)break;
	}
	if(an<100){
		for(int i=1;i<=qpow(a1,b1,1e9);i++){
			rotate();
		}
		for(int i=1;i<=16;i++){
			ans[i]=a[i];
		}
	}
	else{
		for(int i=1;i<=16;i++){
			init();
			int id=getEnd(ch[i]);
			ans[id]=ch[i];
		}
	}
	for(int i=1;i<=16;i++){
		cout<<ans[i];
	}
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}
  • 思路整理：一个三角形魔方可以从三个方向去转动，显然是存在循环的，可以从某一个位置去入手，一个位置经过一次操作序列会到达另一个位置，若该位置是之前在转动过程中已经到达过的，那么显然是构成了循环，因为位置是有限的（16个）因此最多执行操作序列16次就会出现循环，那么利用该循环即可快速找到该位置字符最终的位置。
  • 解题思路：
    • 首先是对于魔方转动的模拟处理
      • 一种是把三角形的魔方映射到二维数组中，参考杨辉三角，然后观察每一个转动的规律来实现模拟，这样的话会比较麻烦，有点烧脑。
      • 一种比较直白的想法，直接映射到一维数组中，然后再图上给A~P按顺序标号，就可以知道每次操作是把谁和谁交换了。
    • 设计一个函数来找循环节，找到循环节后，减去之前已经执行过的操作次数，再去模上循环节，在转动该次数，即可得到当前字符最终的位置。
    • 同时考虑不存在循环节的情况，也就是操作次数小于16时，此时直接暴力转动即可。

课堂练习

公交换乘

#include<bits/stdc++.h>
#define int long long 
using namespace std;
typedef pair<int,int>PII;
typedef pair<PII,int>PPI;
const int N=1e6+5;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
vector<int>E[N];
vector<int>user[N];
struct str{
	int siz,pri,t;
}a[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].siz>>a[i].pri>>a[i].t;
	}
	queue<PII>q;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i].siz==0){
			ans+=a[i].pri;
			q.push({a[i].pri,a[i].t});
		}
		else{
			while(q.size()!=0&&a[i].t-q.front().second>45)q.pop();
			int len=q.size();
			int ok=0;
			for(int j=0;j<len;j++){
				PII f=q.front();
				q.pop();
				if(ok==0&&f.first>=a[i].pri){
					ok=1;
				}
				else q.push(f);
			}
			if(ok==0) {
				ans+=a[i].pri;
			}
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _=1;
	while(_--){
		solve();
	}
}
  • 整理思路：搭乘地铁获得公交优惠卷，坐公交时一定会先使用优惠卷，如果没有满足条件的优惠卷可以用再去花钱。对于优惠卷使用时的限制：1、优惠卷的获得时间与当前公交开始乘坐的时间不得超过45分钟。2、优惠卷对应的地铁价格不得低于当前公交的价格 。3、如果有多张满足前两个条件的，优先用最先获得的优惠卷
  • 解法：对于优惠卷我们需要用一个数据结构去维护，当我们坐公交时从数据结构中找是否存在满足条件的优惠卷。根据条件限制，要求我们优先使用最早获得的，对应我们的queue 。如果存所有的优惠卷然后每次都去一一判断就是超时时间复杂度为：O(n2)O(n^2)，但是我们发现当一个优惠卷因为时间问题不可用时，下一次公交车也一定不会用，所以我们可以提前把因不满足时间的优惠卷给丢出去。这样就是最多45个优惠卷，去找满足条件2的优惠卷即可。最终的时间复杂度为O(45∗n)O(45*n)

密码锁

#include<bits/stdc++.h>
#include <functional>
#define int long long 
using namespace std;
typedef pair<int,int>PII;
typedef pair<PII,int>PPI;
const int N=1e3+5;
vector<vector<int>> cand;

bool canReach(vector<int>P,vector<int>S){
    int cnt=0,pos=-1,pos2=-1;
    for(int i=0;i<5;i++){
        if(P[i]!=S[i]){
            cnt++;
            if(pos==-1)pos=i;
            else if(pos2==-1)pos2=i;
        }
    }
    if(cnt==0)return 0;
    if(cnt==1)return 1;
    if(cnt==2&&pos2==pos+1){
        int d1=(S[pos]-P[pos]+10)%10;
        int d2=(S[pos2]-P[pos2]+10)%10;
        if(d1==d2)return 1;
    }
    return 0;
}
void getPre(vector<int>S,vector<vector<int>>&res){
    for(int i=0;i<5;i++){
        for(int k=1;k<=9;k++){
            vector<int>P=S;
            P[i]=(P[i]-k+10)%10;
            res.push_back(P);
        }
    }

    for(int i=0;i<4;i++){
        for(int k=1;k<=9;k++){
            vector<int>P=S;
            P[i]=(P[i]-k+10)%10;
            P[i+1]=(P[i+1]-k+10)%10;
            res.push_back(P);
        }
    }
}

void solve(){
    int n;
    cin>>n;
    vector<vector<int>>a(n,vector<int>(5));
    for(int i=0;i<n;i++)
        for(int j=0;j<5;j++)
            cin>>a[i][j];
    
    getPre(a[0],cand);
    for(int i=1;i<n;i++){
        vector<vector<int>>nxt;
        for(int j=0;j<cand.size();j++){
            if(canReach(cand[j],a[i]))nxt.push_back(cand[j]);
        }
        cand=nxt;
    }
    cout<<cand.size()<<"\n";
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int _=1;
    while(_--){
        solve();
    }
}

  • 题意理解：给定 n 个"锁后状态"，找一个密码 P，使得每个状态都能从 P 一次操作到达。

  • 整理思路：重点在于每个状态都要从P一次操作达到，意味着要从 每个状态操作一次得到新的集合中找出这些这些集合的交集。

  • 解法：

    • 法1：暴力枚举每个状态操作一次得到的新的集合，并对其中的状态打上标记，最后看那些状态被打上了n次标记，那这个状态就是交集，因此答案就要+1。时间复杂度为O(81∗n+105)O(81*n+10^5)
    • 法2：既然要求交集那么就意味着满足条件的状态一定在第一个锁后状态进行一次操作得到状态集合中，那么我们就可以拿着这个集合去检查有哪些状态是其他锁后状态可以通过一次操作得到的，在经过n次筛选最后剩下的就是答案。

一元二次方程

#include<bits/stdc++.h>
#include <functional>
#define int long long 
using namespace std;
typedef pair<int,int>PII;
typedef pair<PII,int>PPI;
const int N=1e3+5;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

pair<int,int> simplify(int p,int q){
    if(q<0)p=-p,q=-q;
    int g=gcd(abs(p),q);
    return {p/g,q/g};
}

string fmt(int p,int q){
    if(p==0)return "0";
    if(q==1)return to_string(p);
    return to_string(p)+"/"+to_string(q);
}

void solve(){
    int M;
    cin>>M;
    int a,b,c;
    cin>>a>>b>>c;
    int delta=b*b-4*a*c;
    if(delta<0){
        cout<<"NO\n";
        return ;
    }
    int sq=(int)sqrt(delta);
    if(sq*sq==delta){
    
        int s=(a>0?1:-1);
        int num=-b+s*sq;
        int den=2*a;
        PII pii=simplify(num,den);
        cout<<fmt(pii.first,pii.second)<<"\n";
    }
    else{
        
        int k=1,r=delta;
        for(int i=sq;i>=2;i--){
            if(delta%(i*i)==0){
                k=i;
                r=delta/(i*i);
                break;
            }
        }

        PII pii1=simplify(-b,2*a);
        PII pii2=simplify(k,2*abs(a));
		int p1=pii1.first,q1=pii1.second;
		int p2=pii2.first,q2=pii2.second;
        string out="";
        if(p1!=0)out+=fmt(p1,q1)+"+";

        if(p2==q2)out+="sqrt("+to_string(r)+")";
        else if(q2==1)out+=to_string(p2)+"*sqrt("+to_string(r)+")";
        else if(p2==1)out+="sqrt("+to_string(r)+")/"+to_string(q2);
        else out+=to_string(p2)+"*sqrt("+to_string(r)+")/"+to_string(q2);

        cout<<out<<"\n";
    }    
    
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int _=1;
    cin>>_; 
    while(_--){
    	solve();
	}
}
  • 整理思路：给出一个一元二次方程的各项系数，让我们输出他的两个解，如果没有解则输出No。有的话需要我们按照最简的形式给出：p1+p2,其中p1和p2都得是最简，最简定义：分数要化简，开根要化简。
  • 解法：
    • 1、首先根据公式判断是否存在解
    • 2 、有解的情况下要判断Δ是否是完全平方数
    • 3、若不是则不需要加sqrt直接对p1和p2进行分数化简：利用GCD来化简
    • 4、处理Δ不是完全平方数的情况
      • 是否是完全平方数的倍数，是则提取最大的出来变成整数
      • 对p1和p2进行分数化简

儒略日

#include<bits/stdc++.h>
#define int long long
using namespace std;

int md[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

bool leapJ(int y){ return y%4==0; }
bool leapG(int y){ return y%400==0||(y%4==0&&y%100!=0); }

int daysOfYear(int y){
    if(y==1582) return 355;
    bool g=(y>1582);
    int ans;
    if(g) ans=365+leapG(y);
    else ans=365+leapJ(y);
    return ans;
}

void print(int d,int m,int y){
    cout<<d<<" "<<m<<" ";
    if(y<0) cout<<-y<<" BC\n";
    else cout<<y<<"\n";
}

vector<int> pre;  // pre[i] = 年份(i-4713)的1月1日 对应的儒略日r值

void init(){
    pre.push_back(0);  // pre[0]：公元前4713年1月1日，r=0
    int y = -4713;
    int acc = 0;
    while(y <= 5000){
        acc += daysOfYear(y);
        pre.push_back(acc);  // pre[1] = 365，即公元前4712年1月1日对应r=365
        y++;
        if(y == 0) y = 1;
    }
}
void solve(){
	int r;
	cin>>r;
    // 二分找年份：最大的idx使 pre[idx] <= r
    int lo=0, hi=pre.size()-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(pre[mid] <= r){ 
			ans=mid; 
			lo=mid+1; 
		}
        else hi=mid-1;
    }
    // rem = r - pre[ans] + 1，即该年第几天（1-indexed）
    int rem = r - pre[ans] + 1;
    int year = ans - 4713;

    if(year == 1582){
        // 1~9月（儒略历）
        for(int m=1; m<=9; m++){
            int d=md[m];
            if(m==2) d = leapJ(1582)?29:28;
            if(rem <= d){ 
				print(rem,m,year); 
				return; 
			}
            rem -= d;
        }
        // 10月：只有1~4日
        if(rem <= 4){ 
			print(rem,10,year); 
			return; 
		}
        rem -= 4;
        // 11~12月（格里高利历）
        for(int m=11; m<=12; m++){
            if(rem <= md[m]){ print(rem,m,year); return; }
            rem -= md[m];
        }
    }
    else{
        bool g = (year > 1582);
        for(int m=1; m<=12; m++){
            int d=md[m];
            if(m==2) d = (g?leapG(year):leapJ(year))?29:28;
            if(rem <= d){ print(rem,m,year); return; }
            rem -= d;
        }
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    init();
    int _=1;
    cin>>_;
    while(_--){
    	solve();
	} 
}
  • 整理思路：给出儒略日的起始日期 、在 儒略历 和 格里高利历下天数的计算规则。那我们就把时间线分为儒略历时期和 格里高利历 以及特殊时期 那么我们根据上述划分，就可以找到儒略日rir_i所对应的年份，得出年后就可以根据年份来得出具体的月和日
  • 解题思路：
    • 可以发现对于儒略历和格里高利历之间的唯一区别是闰年的判断不同，要想定位到年，那么只用考虑每年具体的天数然后做除法计算即可，那么就按照三个时期来进行计算。
    • 儒略历 是满足4的倍数即为润年。因此计算出1582这个分界线与起始日期之间有多少个4的倍数即可解决，对于格里高利历来说则是4的倍数但不是100的倍数或者是400的倍数即可，也是找出这些数即可解决问题。可以从数学角度来计算a到b之间有多少x的倍数的数
    • 注意由于天数在1e9那么年份就在1e7左右如果暴力去求rir_i对应的年份的话时间上会比较紧张，那么可以考虑二分加速查找。
    • 得出年份后进行分类讨论即可得出月份
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论