第十二屆藍橋杯大賽軟體賽省賽 C/C++ 大學 B 組 填空題

256*1024*1024/4 = 67,108,864

答案 3181

/*模擬一下結果就出來了*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[10];
int main()
{
	for(int i=0;i<10;i++)
	a[i] = 2021;
	
	int res = 1;
	bool flag = true;
	int num;
	
	while(flag)
	{
		int r = res;
		while(r)
		{
			num = r % 10;
			if(!a[num]) //沒有數字 
			{
				flag = false;
				break;
			}
			a[num]--;
			r /= 10;
		}
		if(flag)
		res++;
	}
	
	cout<<res-1<<endl;
	return 0;
}

/*
一條直線就是y = kx + b
我們區分直線的標志就是斜率 k 和截距 b
設兩個點是(x1,y1),(x2,y2)
k = (y2 - y1) / (x2 - x1)
b = -k*x1 + y1
我的思路是一個k對應一個b的set集合
k是好求的，關鍵是b的精度問題
最后把斜率不存在以及斜率為0的直線加起來
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <map>

using namespace std;

map<double,set<double> >mp;

int main()
{
	int xx = 19,yy = 20;
	for(int i=0;i<=xx;i++)
	{
		for(int j=0;j<=yy;j++) //第一個點 
		{
			for(int k=0;k<=xx;k++)
			{
				for(int l=0;l<=yy;l++) //第二個點 
				{
					if(i == k || j == l) continue;
					
					double x = (double)(i - k);
					double y = (double)(j - l);
					double z = y * 1.0 / x;  
				//	double b = (double)(j - z*i);  //這樣記錄 b 結果是 47753，我比賽用的是這個，可能錯了！


				//  k = (y2 - y1) / (x2 - x1)把這個運算式代入b = -k*x1 + y1在化簡
					double b = ((double)(k*j) - (double)(i*l)) / (i-k);   //這個結果是 40257 好像這樣更對 
					mp[z].insert(b); 
				}
			}
		}
	}
	
	int res = 0;
	map<double,set<double> >::iterator it = mp.begin();
	
	for(;it!=mp.end();it++)
	{
		res += it->second.size();
	}
	
	cout<<res + xx + 1 + yy + 1<<endl;
	return 0;
}

答案是2430

/*沒寫出來...我的思路是分解質因子，然后排列組合，但是有更暴力的方法直接求因子，然后三重回圈遍歷因子就出來了*/

//這是求出的質因子
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

map<int,int>mp;
typedef long long ll;
int main()
{
	ll num = 2021041820210418;
	
	for(int i=2;i<100000;i++)
	{
		if(num % i == 0)
		{
			while(num % i == 0)
			{
				num /= i;
				mp[i]++;
			}
		}
	}
	if(num != 0)
	mp[num]++;
	
	map<int,int>::iterator it = mp.begin();
	for(;it != mp.end();it++)
	{
		cout<<it->first<< " " <<it->second<<endl;
	}
	return 0;
}

/*兩重回圈就出來了......太暴力了*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;
ll num = 2021041820210418;
ll arr[100000];

int main()
{
    int index = 0;
    for(int i=1;i<=sqrt(num);i++)
    {
        if(num % i == 0)
        {
            arr[index++] = i;
            arr[index++] = num / i;
        }
    }    

    int res = 0;
    for(int i=0;i<index;i++){
        for(int j=0;j<index;j++)
        if(num % (arr[i] * arr[j]) == 0)
        res++;
    }

    cout<<res<<endl;
    return 0;
}

答案 10266837

/*直接上Dijkstra*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 2022;
int vel[maxn][maxn];
vector<int>g[maxn];
bool sign[maxn];
int dis[maxn];

struct node{
	int n_dis;
	int id;
	bool operator < (const node &a) const{
		return a.n_dis < n_dis;
	}
}; 
int gcd(int a,int b)
{
	if(b == 0) return a;
	return gcd(b,a%b);
}
void dijkstra(int s)
{
	for(int i=1;i<maxn;i++)
	dis[i] = 1000000000,sign[i] = false;
	
	dis[s] = 0;
	priority_queue<node>q;
	node h;
	h.id = 1,h.n_dis = 0;
	q.push(h);
	
	while(!q.empty())
	{
		node u = q.top();
		q.pop();
		
		if(sign[u.id]) continue;
		sign[u.id] = true;
		
		
		for(int i=0;i<g[u.id].size();i++)
		{
			int j = g[u.id][i];

			if(sign[j]) continue;
			
			if(vel[u.id][j] + u.n_dis < dis[j])
			{
				dis[j] = h.n_dis = vel[u.id][j] + u.n_dis;
				h.id = j;
				q.push(h);
			}
		}
	}
}
int main()
{
	//建圖
	for(int i=1;i<maxn;i++)
	{
		for(int j=1+i;j<maxn;j++)
		{
			if(abs(i-j) <= 21)
			{
				int num = gcd(i,j);
				g[i].push_back(j),g[j].push_back(i);
				vel[i][j] = vel[j][i] = i*j/num;
			}
		}
	}
	
	/*
	for(int i=1;i<maxn;i++)
	cout<<g[i].size()<<endl;
	*/
	dijkstra(1);
	
	for(int i=1;i<maxn;i++)
	cout<<dis[i]<<endl;
	
	cout<<"2021 = "<<dis[2021]<<endl;
	return 0;
}