1.字串排序
不会做，感觉挺难的，有兴趣的可以看下面题解
#include <iostream>
#include <string.h>
using namespace std;
int V;
int len;//符合交换次数V，字符串长度最小值
int now; //当前已经构造好的那一部分字符串逆序对个数
int cnt[27];//当前位置后续部分包含字母a~z个数
int sum[27];//当前构造的部分字符串包含字母a~z个数//根据V算出字符串长度
int get_max(int len){return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
//当前放字母x,后边还有n个位置，看是否满足V
bool check(int x , int n)
{memset(cnt , 0 , sizeof(cnt));int add1 = 0;//在当前位置放x,新增的逆序对个数int add2 = 0;//在当前位置放x,后边的逆序对个数最大值for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];//当前位置放x,sum[x]++sum[x] ++ ;//后边剩余n个位置，遍历for(int L = 1 ; L <= n ; L ++){int ma = -1;//后续L位置上，放字母新增逆序对个数最大值int pos = 0;//放置的字母int num = 0;//已经放置的大于第j个字母的字符个数for(int j = 26 ; j >= 1 ; j --){if(L - 1 - cnt[j] + num> ma){ ma = L - 1 - cnt[j] + num;pos = j;}num += sum[j];}add2 += ma;cnt[pos] ++;//x后续部分包含字母a~z个数}if(now + add1 + add2 >= V) {now += add1; //当前已经构造好的那一部分字符串逆序对个数return true;}else {sum[x] -- ;//放弃在当前位置放置xreturn false;}
}
int main()
{string ans = "";cin >> V;//从1开始枚举长度，直到len可以产生的最大逆序对大于Vfor(int i = 1 ; ; i ++) {if(get_max(i) >= V){len = i;break ;}}//构造字符串ans，从i开始枚举，枚举每个位置上的字母，字典序小for(int i = 1 ; i <= len ; i ++){for(int j = 1 ; j <= 26 ; j ++){if(check(j , len - i)){ans += char(j + 'a' - 1);break ;}}}cout << ans << '\n';return 0;
}2.门派制作
签到水题
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum=0;
signed main()
{for(int i=2; i<=2020; i++){string s=to_string(i);for(auto t:s){if(t=='2'){sum++;}}}cout<<sum<<endl;return 0;
}
3.既分约数
签到水题
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum=0;
signed main()
{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;
}
4.蛇形填数
打表找规律
//1
//5
//13
//25
//41
//n*n+(n-1)*(n-1);
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main()
{cout<<20*20+19*19<<endl;return 0;
}5.跑步锻炼
日期题，注意周几判断：x%7==1 （额外提一下：类似的方向判断 x%360）和 闰年
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool fun1(int t1)
{if(t1%4==0 && t1%100!=0 || t1%400==0){return true;}return false;
}
bool fun(int t)
{int m[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};int year=t/10000,month=t%10000/100,day=t%10000%100;if(fun1(year)) //判断闰月{m[2]=29;}if(year>=2000 && year<=2020 && month>=1 && month<=12 && day>=1 && day<=m[month]){return true;}return false;
}
signed main()
{int sum=0,x=6;for(int i=20000101; i<=20201001; i++){if(fun(i)) //是否为合法日期{if((x%7)==1 || i%10000%100==1) //周1或初1{sum+=2;}else{sum+=1;}x++; //判断周几}}cout<<sum<<endl;return 0;
}
6.七段码
直接把所有情况找出来，最容易理解掌握的方法
#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{// 请在此输入您的代码int sum = 0;//有一段二极管发光; a,b,c,d,e,f,gint l1 = 7;//有两段二极管发光; ab,af,bc,bg,cg,cd,de,eg,ef,fgint l2 = 10;//有三段二极管发光; abf,abc,abg,afg,afe,bcd,bcg,bgf,bge,cgd,cgf,cge,cde,cdg,deg,def,efgint l3 = 16;// //有四段二极管发光; abcd,abcg,abcf,abge,abgf,abfe,afeg,bcde,bcdg,bcgf,bcge,bged,bgef,cdef,cdeg,cdgf,cgfa,cgfe,defg,defaint l4 = 20;//有五段二极管发光即有两端不发光; ab,ac,ad,ae,af,ag,bc,bd,be,bg,cd,cf,cg,de,df,dg,ef,eg,fgint l5 = 19;////有六段二极管发光即有一端不发光; a,b,c,d,e,f,gint l6 = 7;//(找一段二极管不发光的：)//第七种情况，全部发光int l7 = 1;sum = l1 + l2 + l3 + l4 + l5 + l6 + l7;printf("%d\n", sum);return 0;
}7.成绩统计
签到水题，注意使用printf里面的 .lf 以此达到四舍五入的效果
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans1=0,ans2=0;
signed main()
{cin>>n;for(int i=1;i<=n;i++){int num;cin>>num;if(num>=60){ans1++;}if(num>=85){ans2++;}}printf("%.lf%\n",100.0*ans1/n) ;printf("%.lf%\n",100.0*ans2/n) ;return 0;
}8.回文日期
暴力枚举所有情况，寻找回文日期，但是还有一种简单的方法是利用回文特性，通过月日反推出年份，但我感觉有问题（对于闰月判断不是很明确）下面两个代码都给出
#include<bits/stdc++.h>
#define int long long
using namespace std;int d1, d2, sum = 0;bool fun1(int t1)
{if (t1 % 4 == 0 && t1 % 100 != 0 || t1 % 400 == 0){return true;}return false;
}bool fun(int t)
{int m[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int year = t / 10000, month = t % 10000 / 100, day = t % 10000 % 100;if (fun1(year)) // 判断闰年{m[2] = 29;}if (month >= 1 && month <= 12 && day >= 1 && day <= m[month]){return true;}return false;
}bool isPalindrome(int t)
{int original = t;int reversed = 0;// 判断数字是否回文while (t > 0){int digit = t % 10;reversed = reversed * 10 + digit;t /= 10;}return original == reversed;
}signed main()
{cin >> d1 >> d2;for (int i = d1; i <= d2; i++){if (fun(i)) // 判断日期合法{if (isPalindrome(i)) // 判断回文{sum++;}}}cout << sum << endl;return 0;
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
int date1,date2,sum=0;
signed main()
{cin>>date1>>date2; //回文：年=月+日（所有月日组合，看年份是否满足）int m[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31};for(int month=1; month<=12; month++){for(int day=1; day<=m[month]; day++){int year1=day%10*1000+day/10*100+month%10*10+month/10;int date=year1*10000+month*100+day; if(date>=date1 && date<=date2){sum++;}}}cout<<sum<<endl;return 0;
}
9.子串分值和
可以去看我的上一篇博客，关于贡献法的题型
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
char s[N];
int pos[27]; //记录该字符上一次出现的位置
signed main()
{cin>>s+1; //索引1开始完整读取int n=strlen(s+1);int res=0;for(int i=1; i<=n; i++){ int t=s[i]-'a';res+=(int)(i-pos[t])*(n-i+1); //n-i+1加一是为了包括自己pos[t]=i; //只有最左边的那个会被计入贡献}cout<<res<<endl;return 0;
}
10.平面切分
三种情况：初始状态没有直线，1块平面（切平面算块数）
1.如果新直线和之前的某条直线重合（比如两条一模一样的直线），不增加块数（因为相当于没加新东西）。
2.如果新直线和之前的某条直线平行但不重合，增加 1 块（因为平行直线不会相交，只会多切一刀）。
3.如果新直线和之前的直线相交，每有一个新的交点（注意：多个直线交于同一点只算一个），增加的块数 = 交点数 + 1。
#include<bits/stdc++.h>
#define int long long
using namespace std;
double s[1010][2]; //存储直线的A（斜率）和B（截距）
int ans; //存储当前的部分
bool st[1010]; //标记重边
int n;
pair<double,double>p;
signed main()
{cin>>n;for(int i=0; i<n; i++){cin>>s[i][0]>>s[i][1];set<pair<double,double>>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<<endl;return 0;
}
