“思特奇杯”编程之星初赛

“思特奇杯”编程之星初赛

第一题
#include
using namespace std;
int main()
{
int sum=0;
for(int i=1;i<=2020;i++)
{
int k=i;
int m=i;
int x=1000;
while(m!=0)
{
k=m/x;
m=m%x;
x/=10;
if(k==2)
{
sum++;
}
}
}
cout << sum << endl;
return 0;
}

第二题

#include
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}

int main()
{
int sum=0;
for(int i=1;i<=2020;i++)
for(int j=1;j<=2020;j++)
{
if(gcd(i,j)==1)
{
sum++;
}
}
cout << sum << endl;
return 0;
}

第三题

#include
using namespace std;
int check(int a,int b)
{
int str[100][100];
int sum=1;
int x,y;
for(int i=1;i<=50;i++)
{
if(i%2==1)
{
for(x=i,y=1;x>=1&&y<=i;x–,y++)
{
str[x][y]=sum++;
}
}
else{
for(x=1,y=i;x<=i&&y>=1;x++,y–)
{
str[x][y]=sum++;
}
}
}
return str[a][b];
}
int main()
{
int row,line;
cin >> line >> row;
cout << check(line,row) << endl;
return 0;
}

第四题

#include
using namespace std;
int judge(int year)
{
if((year%40&&year%100!=0)||year%4000)
{
return 1;
}
else return 0;
}
int main()
{
int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int y,m,d;
int w=6;
int step=0;
for(y=2000;y<=2020;y++)
for(m=1;m<=12;m++)
for(d=1;d<=day[m]+((m2)?judge(y):0);d++,w=w%7+1)
{
step++;
if(d1||w1) step++;
if(y2020&&m10&&d1)
{
cout << step << endl;
}
}
return 0;
}

第五题

//a-1,b-2,c-3,d-4,e-5,f-6,g-7
#include
using namespace std;
bool con[8][8];
int father[8];
int sum=0;
bool vis[8];
int find(int n)//并查集
{
if(father[n]==n)
{
return n;
}
else{
father[n]=find(father[n]);//路径压缩
return father[n];
}
}
void dfs(int t)//枚举过程
{
if(t>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(vis[i]&&vis[j]&&con[i][j])
{
int x=find(i),y=find(j);
if(x!=y)
{
father[x]=y;//改变父类
}
}
}
int k=0;
for(int i=1;i<=7;i++)
{
if(vis[i]&&father[i]i) k++;//全体元素只有一个根
}
if(k1) sum++;
return;
}
//DFS中典型的二叉树形搜索树
vis[t]=1;
dfs(t+1);
vis[t]=0;
dfs(t+1);
}
int main()
{
con[1][2]=con[1][6]=1;
con[2][1]=con[2][7]=con[2][3]=1;
con[3][7]=con[3][4]=con[3][2]=1;
con[4][5]=con[4][3]=1;
con[5][4]=con[5][7]=con[5][6]=1;
con[6][1]=con[6][7]=con[6][5]=1;
con[7][6]=con[7][5]=con[7][2]=con[7][3]=1;
dfs(1);
cout << sum << endl;
return 0;
}

第六题

#include
using namespace std;
int num[10005];
float a,c;
int main()
{
int n;
cin >> n;
for(int i=0;i {
cin >> num[i];
if(num[i]>=60) c++;
if(num[i]>=85) a++;
}
float x=(c/n+0.005)*100;
float y=(a/n+0.005)*100;
cout << (int)x << “%” << endl;
cout << (int)y << “%” << endl;
}

第七题

#include
using namespace std;
int str[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool y1=false,y2=false;
bool judge1(int year)
{
if((year%40&&year%100!=0)||year%4000)
return true;
else{
return false;
}
}
bool judge2(int x)
{
int s[8];
int m=1000000;
int n=10;
s[0]=x/10000000;
for(int i=1;i<8;i++,m/=10)
{
s[i]=x/m%n;
}
for(int i=0,j=7;i<=3;i++,j–)
{
if(s[i]!=s[j])
{
return false;
}
}
return true;
}
bool judge3(int x)
{
int s[8];
int m=1000000;
int n=10;
s[0]=x/10000000;
for(int i=1;i<8;i++,m/=10)
{
s[i]=x/m%n;
}
if(s[0]==s[2]&&s[2]==s[5]&&s[5]==s[7]&&s[1]==s[3]&&s[3]==s[4]&&s[4]==s[6])
{
return true;
}
else return false;
}

void research(int year,int month,int day);
int main()
{
int x;
cin >> x;
int year=x/10000;
int month=x%10000/100;
int day=x%100;
bool x1=judge2(x);
if(x1=true) day++;
research(year,month,day);
return 0;
}
void research(int year,int month,int day)
{
for(int a=year;a<9000;a++,month=1,day=1)
{
int k=0;
if(judge1(a)) k++;
for(int b=month;b<=12;b++)
for(int c=day;c<=str[b]+((b==2)?k:0);c++)
{
int y=a10000+b100+c;
if(judge2(y)&&!y1)
{
y1=true;
cout << y << endl;
}
if(judge3(y)&&!y2)
{
y2=true;
cout << y << endl;
}
if(y1&&y2)
{
break;
}
}
}
}

第八题

#include
#include
using namespace std;
int main()
{
string str;
int sum=0;
cin >> str;
int length=str.length();
for(int i=0;i {
set p;
for(int j=i;j {
p.insert(str[j]);
sum+=p.size();
}
}
cout << sum << endl;
return 0;
}

第九题

#include
using namespace std;
double s[1010][2];
bool st[1010];
long ans=1;//开始有一面
struct parameter
{
double first;
double second;
};
bool operator<(const parameter& x,const parameter& y){//因为要使用结构set，所以要重载<
if(x.first < y.first||x.second < y.second)
return true;
return false;
}
int main()
{
int n;
cin >> n;
for(int i=0;i {
cin >> s[i][0] >> s[i][1];
parameter p;
set point;//解决点重合
for(int j=0;j {
if(st[j]) continue;
if(s[i][0]==s[j][0])
{
if(s[i][1]==s[j][1])
{
st[j]=true;//解决线重合
break;
}
else {
continue;
}
}
//计算交点
p.first=(s[j][1]-s[i][1])/(s[i][0]-s[j][0]);
p.second=(s[i][1]*s[j][0]-s[j][1]*s[i][0])/(s[j][0]-s[i][0]);
point.insert§;
}
if(!st[i])ans+=point.size()+1;
}
cout << ans << endl;
return 0;
}

第十题

#include
using namespace std;
const int N = (int)1e4+5;
int num[N];//存放每个字母对应输出个数
int main()
{
int n, m;
int _max, id, len, sum;//_max最大字母序号，sum是逆序数
scanf("%d", &n);
sum = 0; len = 0;//len为给定逆序数所需的最小字符长度
while (sum < n)//拿逆序数sum来卡循环
{
id = 1;
for (int i = 2; i <= 26; i++)
{
if (num[i] < num[id])
{
id = i;
}
}
sum = sum + len - num[id];
len ++;//确定长度
num[id] ++;
}
for (int i = 1; i <= 26; i++)//找到_max,即最大字母序号
{
if (num[i]) {
_max = i;
}
}
m = sum - n; //逆序数差值,即需要剪掉的部分(最大逆序数是sum，而指定的是n，说明还待处理的有m)
/具体处理m的方式：若m为0，则不需要处理，若不为0，因为在字符最短的情况下求字典序最小的序列，
那么就从字典序大的开始，和字典序小的进行转换/
for (int i = 1; i <= m; i++)//成功处理m次
{
for (int j = _max; j >= 1; j–)
{
id = 0;
while(num[++id]!= num[j]);//从最小的开始找输出个数和_max一样的，具体原因可以自行思考一下(每次成功处理一次)
if (id != j)//具体处理 *** 作
{
num[id] ++;
num[j] --;
break;
}
}
if (!num[_max])
{
_max–;
}
}
//正确输出
for (int i = _max; i >= 1; i–)//字母
{
for (int j = 0; j < num[i]; j++)//个数
{
printf("%c", ‘a’+i-1);
}
}
printf("n");
return 0;
}