【思特奇杯·云上蓝桥-算法集训营】

第一题：门牌制作第二题：既约分数第三题：蛇形填数第四题：跑步锻炼第五题：七段码第六题：成绩统计第七题：回文日期第八题：子串分值和第九题：平面切分第十题：字串排序

#include
using namespace std;
int calu(int num)
{
	int ans = 0;
	while(num)
	{
		if(num%10==2)
			ans++;
		num/=10;
	}
	return ans;
}
int main()
{
	int cnt = 0;
	for(int i = 1; i <=2020; i++)
	{
		cnt+=calu(i);
	}
	cout << cnt < 
第二题：既约分数 
#include
using namespace std;

int gcd(int a,int b)
{
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}
int main()
{
	int ans = 0;
	for(int i = 1; i <= 2020; i++)
	{
		for(int j = 1; j <= 2020; j++)
		{
			if(gcd(i,j)==1)
			{
				ans++;
			}
		}
	}
	cout << ans < 
第三题：蛇形填数 
#include

using namespace std;

int main()
{
	//首先计算第20行20列位于三角形第几行，用公式算出是2*20-1=39行
	//计算39行的最后一个数 
	int n = 20;
	n = n*2-1;
	int ans = 0,sum =  0;
	for(int i = 1; i <=n ;i++)
	{
		sum+=i; 
	} 
	ans = (sum+sum-n+1)/2;
	cout << ans < 
第四题：跑步锻炼 
#include

using namespace std;
int run(int year)
{
	return (year%400==0)||(year%4==0&&year%100!=0);
}
int main()
{
	int monNum = 0,weekNum = 0,monWeek = 0,days = 0,ans = 0;
	int monDay[13] = {0,31,30,31,30,31,30,31,31,30,31,30,31};
	for(int i = 2000; i <= 2020; i++)
	{
		//闰年处理 
		if(run(i)) 
			monDay[2] = 29;
		else 
			monDay[2] = 28;
		//计算总天数和月份 
		for(int j = 1; j <= 12; j++)
		{
			if(i==2020&&j==10) break;
			monNum += 1;
			days+=monDay[j];
			if((days+1)%7==3)
			{
				monWeek++;
			}
			
		}
	} 
	weekNum += days/7;
	if(days%7>=3) 
		weekNum++;
	//cout << days+1 << ends << weekNum < 
第五题：七段码 
#include
using namespace std;
int use[10];
int ans,e[10][10],father[10];
void init()
{
	//连边建图
	//a b c d e f g
	//1 2 3 4 5 6 7
	e[1][2]=e[1][6]=1;
	e[2][1]=e[2][7]=e[2][3]=1;
	e[3][2]=e[3][4]=e[3][7]=1;
	e[4][3]=e[4][5]=1;
	e[5][4]=e[5][6]=e[5][7]=1;
	e[6][1]=e[6][5]=e[6][7]=1;
}
int find(int a)//并查集
{
	if(father[a]==a)
	{
		return a;
	}
	father[a]=find(father[a]);
	return father[a];
}
void dfs(int d)
{
	if(d>7)
    {
		
		for(int i=1;i<=7;i++)
        {
            father[i]=i;
        }
		for(int i=1;i<=7;i++)
        {
		    for(int j=1;j<=7;j++)
            {  
                if(e[i][j]&&use[i]&&use[j])
                {
                    int fx=find(i),fy=find(j);
                    if(fx!=fy)
                    {
                        father[fx]=fy;
                    }
			    }
            }
			
        }
		int k=0;
		for(int i=1;i<=7;i++)
        {
            if(use[i]&&father[i]==i)
            {
                k++;
            }
        }
		if(k==1)
        {
            ans++;
        }
		return;
	}
	use[d]=1;
	dfs(d+1);
	use[d]=0;
	dfs(d+1);
}
int main()
{
	init();
	dfs(1);
	cout< 
第六题：成绩统计 
#include
#include
struct line
{int hao[100];
 char name[100][20];
 int  score[100][3];
 int n;
 float avr[100];
}Stu;
int main()
{struct line Stu={{0},{''},{0},0,{0}};
     int i,j,k;
   	scanf("%d",&Stu.n);
	for(i=0;iStu.hao[j+1])))
	    {temp=Stu.avr[j];
	     Stu.avr[j]=Stu.avr[j+1];
	     Stu.avr[j+1]=temp;
	     strcpy(t,Stu.name[j+1]);
	     strcpy(Stu.name[j+1],Stu.name[j]);
	     strcpy(Stu.name[j],t);
	     temp=Stu.hao[j];
	     Stu.hao[j]=Stu.hao[j+1];
	     Stu.hao[j+1]=temp;
		}
		}
		for(i=0;i 
第七题：回文日期 
#include
#include
#include
using namespace std;
int month[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int run(int x)
{
    if(x%400==0||(x%4==0)&&(x%100!=0))
        return 1;
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    int a=n/10000;
    for(int i=a;; i++)
    {
        int b=i/1000;
        int c=i/100%10;
        int d=i/10%10;
        int e=i%10;
        int f=e*10+d;
        int g=c*10+b;
        if(run(i))
            month[2]=29;
        if(f<=12&&g<=month[f])
        {
            printf("%d%02d%02dn",i,f,g);
            break;
        }
    }
    for(int j=a;; j++)
    {
        int b1=j/1000;
        int c1=j/100%10;
        int d1=j/10%10;
        int e1=j%10;
        int f1=e1*10+d1;
        int g1=c1*10+b1;
        if(run(j))
            month[2]=29;
        if(f1<=12&&g1<=month[f1]&&(b1==d1)&&(c1==e1)&&(e1*d1==c1*b1)&&(d1*e1==b1*c1))
        {
            printf("%d%02d%02dn",j,f1,g1);
            break;
        }
    }
    return 0;
}
 
第八题：子串分值和 
#include
#include
#include

using namespace std;

int main()
{

    long long int ans=0;
    char s[100005];
    int vis[26]={0};
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i e;
        for(int j=i;j 
第九题：平面切分 
#include
#include
using namespace std;

long double s[1010][2];
long long ans;
bool st[1010];
pair p;


int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i][0] >> s[i][1];
		set> points;

		for (int j = 0; j < i; j++) {//依次比较 查找重边
			if (st[j])continue;//直线是重边
			if (s[i][0] == s[j][0]) {//斜率相同
				if (s[i][1] == s[j][1])
				{
					st[i] = true;
					break;
				}
				else continue;
			}
		p.first = (s[j][1] - s[i][1]) / (s[i][0] - s[j][0]);//交点的x坐标 
		p.second = s[i][0] * p.first + s[i][1];//交点的y坐标 
		points.insert(p);
		}
		if (!st[i])ans += points.size() + 1;//若不是重边，更新答案
	}
	cout << ans + 1;
}
 
第十题：字串排序 
#include 
#include 
#include 

using namespace std;

const int N = 135, M = 10010;

int f[N][30][N];
//chcnt[i][j]记录第i个位置取字母j+'a'的逆序对最大值 
int chcnt[N][30];
//mlen[i]记录每个位置的最大值 
int mlen[N];

void dp()
{
	for (int i = 2; i < N; ++i)
	{
		int m = 0;
		for (int j = 1; j <= 'z' - 'a'; ++j)
		{
			for (int k = 1; k < i; ++k)
			{
				if (k > 1) f[i][j][k] = f[i - 1][j][k - 1] + i - k;
				else f[i][j][k] = chcnt[i - 1][j - 1] + i - 1;
				chcnt[i][j] = max(chcnt[i][j], f[i][j][k]);
			}
			m = max(m, chcnt[i][j]);
		}
		mlen[i] = m;
	}

}

int main()
{
	dp();

	int score = 0;
	cin >> score;
	//找出最短长度值
	int beg = 0;
	for (int i = 1; i < N; ++i)
		if (mlen[i] >= score)
		{
			beg = i;
			break;
		}

	int curr = 0;	//用于记录逆序值
	int same = 1;	//记录后缀中有多少个相同字母
	char last = 'z' + 1;//记录上一个字母是什么 
	for (int i = beg; i > 0; --i)
	{
		//从a开始枚举
		int j = 0;
		for (; j <= last - 'a'; ++j)
		{
			if (j == last - 'a') curr -= same;
			if (curr + chcnt[i][j] >= score)
			{
				curr += i - 1;
				break;
			}
		}
		if (j == last - 'a') same++;
		else
		{
			last = j + 'a';
			same = 1;
		}
		cout << last;
	}
	cout << endl;

	return 0;
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5714524.html