“九韶杯”河科院程序设计协会第一届程序设计竞赛
6的个数
题意：
问你从1到2021出现了多少个数字6
思路：
签到题，莽暴力就完辽
print(602)
小明的作业
题意：
小明同学正在学习一种新的语言。在该语言中，如果出现了一次wa或者一次aw，则代表出现了一个警告。如果出现了连续的wa或者连续的aw，则代表出现了一个错误。小明由于学习比较粗心，所以他想要知道自己刚刚写完的作业中一共出现了多少处警告和错误。下面是小明刚刚写完的作业，请你帮助小明找到他一共出现了多少次警告和多少次错误。
abcwaawawawa中出现了一次警告(wa)和一次错误(awawaw)
abcdefg中没有出现一次警告和错误
waawwaawwawa中出现了四次警告(两次wa和两次aw)和一次错误(wawa)
awawwawa中只出现了两次错误(awaw和wawa)
思路：
没好好读题而错失五分，嗯，下次一定要好好读题(╥﹏╥)
用一个“指针”从头扫一遍，如果连续两个是wa，就判断后两个是不是也是wa，如果是就让wa的答案加一，然后跳到下一个不是wa的地方；如果不是wa，就让aw加一，指针移动2
对于另一种aw的情况同上
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 5000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
string s;
int main(){
cin>>s;
int wa = 0, aw = 0;
for(int i = 0; i < s.size() && i != -1;){
if(s[i] == 'w' && s[i + 1] == 'a'){
if(s[i + 2] == 'w' && s[i + 3] == 'a'){
++wa;
i += 4;
while (s[i] == 'w' && s[i + 1 ] == 'a') {
i += 2;
}
}
else {
++aw;
i += 2;
}
}
else if(s[i] == 'a' && s[i + 1] == 'w'){
if(s[i + 2] == 'a' && s[i + 3] == 'w'){
++wa;
i += 4;
while (s[i] == 'a' && s[i + 1] == 'w') {
i += 2;
}
}
else {
++aw;
i += 2;
}
}
else ++i;
}
cout<<aw<<endl<<wa<<endl;
return 0;
}
/*
iawaswapwauawhawdwafwanbiopwanivgbikvblvbwawawawvolyuvgbololvolgbyolgyowagbolgawgboplwawaolgyolwaogblwaygbowawagwabwayawopwawagyowabwaowapjwapcfrtuywawacvujwawawaufttyfuftywawawatifgugbgbyguwawawawayugbigwwwytigwygwgbwyoawawgoghwaogwborgrewabouyhwabyuhowabhnwawauygbawyawuwaoawfcawaaaahwaywauwagwawefwaafmbawklawjiawihnwanhawawawawijwajiofjeriofgjrefjhwaewarwaowagwahwauwaiwarwaiwaqwarwahwaqwawwaowapfweofbwewafwahwaiwaewawwawawawawafwawawawaeiufwepfhnewfwahwajwatwafowawajtokshwawafwaiwahwafwahmgoewawawawafkfjkewnwawafiewhfwawawafjkernhawkrenwawawawafujnrheiowanwakawawawawwanoifewajrwaoawawfweojnwawawawawawawafjkwenawawferkwmpwawawawaforeijawawferhfiueorghwuwafguwe***aghrwiufgwahweofgowaidwiweaiwwawieyiwe
*/
斐波那契
题意：
小明最近痴迷于斐波那契数列（1，1，2，3，5……），但是最近他又有了新的奇思妙想，就是对于斐波那契数列的相邻的两个数相乘取倒数然后将每一项进行相加，由于小明只喜欢思考不喜欢动手，所以现在他想让你帮他算下这样一个新的数列的前13项的和为多少？（结果用分数表示，且保留最简分数）
思路：
通分之后得到
$$
然后就可以直接用循环莽他o(≧v≦)o
记得最后写个gcd求最大公约数来进行分式约分
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
ll ans = 1;
ll gcd(ll a, ll b){
if(b)return gcd(b, a % b);
else return a;
}
int main(){
// cout<<"6535086616739/3684083162760\n";
int tr[100];
tr[1] = 1;tr[2] = 1;
for(int i = 3; i <= 15; ++i){
tr[i] = tr[i - 1] + tr[i - 2];
}
for(int i = 1; i <= 14; ++i)ans *= tr[i];
// cout<<ans<<endl;
ll sum = 0;
for(int i = 2; i <= 14; ++i){
sum += ans / (tr[i] * tr[i - 1]);
}
cout<<ans<<endl;
cout<<sum<<endl;
cout<<sum / gcd(sum, ans)<<'/'<<ans / gcd(sum, ans)<<endl;
return 0;
}
数列重组
题意：
小明同学最近喜欢上了排列组合，但是现在有这样的一道题把他难住了，已知有一组数字（2，5，3，6，3，6，7，3，7，8）共10个，对于这组数字进行排列后，可以将排列好的数字分为三个部分，且三个部分都是分别有序的（升序或逆序），小明想知道能够有满足条件的多少种排列方式?
思路：
当时一直在想这个题有什么规律，正着来逆着来都想过，但是感觉不太行。
结果谁知道这题就是个大暴力？？
对所有的全排列去枚举两个分割点，判断是否符合题意
这次还学到了一个函数：
is_sorted(tr + l,tr + r, cmp)
判断 tr 数组的 l 到 r 的区间是否按照cmp函数的方法进行的排序，忽律cmp时，就默认从小到大
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 5000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
bool cmp(int x, int y){
return x > y;
}
int tr[] = {2, 3, 3, 3, 5, 6, 6, 7, 7, 8};
int main(){
int ans = 0;
do{
bool judge = 0;
for(int i = 0; i <= 7; ++i){
for(int j = i + 1; j <= 8; ++j){
if((is_sorted(tr, tr + 1 + i) || is_sorted(tr, tr + i + 1, cmp))
&&(is_sorted(tr + 1 + i, tr + 1 + j) || is_sorted(tr + 1 + i, tr + 1 + j, cmp))
&& (is_sorted(tr + 1 + j, tr + 10) || is_sorted(tr + 1 + j, tr + 10, cmp))){
judge = 1;
break;
}
}
if(judge)break;
}
if(judge)++ans;
}while (next_permutation(tr, tr + 10));
cout<<ans<<endl;
return 0;
}
三角形个数
题意：
坤坤给你一个边长为n的等边三角形图形，请你查出图形内等边三角形的个数。 因为数据过大，所以要求答案对1e9+7取模。
思路：
每多一行，就会贡献出一些正三角形和倒三角形，所以只需要记录每一行贡献的三角形的数量即可
观察得：每一行贡献的正三角形的数量为(n + 1) * n / 2
而逆三角形贡献的数量也是有规律滴：
公差为-2的等差数列
第 i 行的通项公式为
通过求和公式
所以得第 i 行的逆三角形数量的求和公式
由观察得：
所以
第 i 行贡献的逆三角的数量为：
综上所述：
第i行贡献第三角形的数量为：
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 5000 + 50
#define endl '\n'
//#define mod 1000000007
const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
ll n, m;
int main(){
n = 20210411;
ll sum = 0;
for(ll i = 1; i <= n; ++i){
m = i / 2;
ll a = ((i + 1) * i / 2) % mod;
ll b = ((i - m) * m) % mod;
sum += (a + b + mod) % mod;
sum %= mod;
}
cout<<sum<<endl;
return 0;
} 记得开longlong，不然就算你公式推对了，也是必wa，耶稣都救不了你
字符串
题意：
又是努力刷题的一天。众所周知wyk是国一大佬喜欢帮群友解答问题。
现在xmy好奇群里的聊天记录有多少条是@wyk的，但是他在忙着摸鱼。
所以找到了你，给了你N条聊天记录，让你帮他算一下。
注意：保证聊天记录的字母都是在ASSIC内。聊天记录存在空格，也可能以空格开头或结尾。@wyk必须连续才能生效，一条聊天记录保证在一行。
思路：
签到题，无限find即可
需要注意的是，输入字符串之前getchar一下，不然你会发现死活输不进去最后一个字符串(///▽///)
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
string s, ss;
int main(){
int t;
cin>>t;
getchar();
int ans = 0;
ss = "@wyk";
while (t--) {
getline(cin,s);
if(s.find(ss) != -1){
++ans;
}
}
cout<<ans<<endl;
return 0;
}
/*
10
abcbdaasddwj@wyk
dasdsafav@Alan
acdbbd@alan@wyk
@zbrnb
??CC??
abababab
wgyyds
@wykyyds
@wyk 111
endcccc@wyk
*/
最强对手矩阵
题意：
这一天你来到了蓝桥杯的考场，你发现考场是一个N*M的矩阵。
因为你的群友很多，你知道考场内每个人有多强，并且把实力换算成了数值。(因为有的人太弱了,所以可能出现实力值是负数的可能)
你想知道考场内实力总和最大的矩阵区域的实力和是多少。
（注意:区域是按照矩形划分的）
思路：
比赛的时候我是打暴力，就是枚举x1，y1，x2，y2，并采用二维前缀和进行了优化，得到了百分之四十的分，时间复杂度是
而正解的方法是枚举行的位置，然后再通过对行进行类似于连续的最大子串的dp来优化时间复杂度，时间复杂度是
先对每列求其前缀和，然后第一层for循环循环的是上行的位置，第二层for循环循环的是下行的位置，然后再一层for循环就进行类dp操作
此时能拿百分之七十的分
剩下的三十分，是这个题的数据范围比较恶心，n*m<=2e5，就有可能是n = 1，m = 2e5，就没办法开二维数组，不然会爆！同样的，可能是n = 2e5 , m = 1，此时就时间复杂度又过不去了，所以，我们对n > m 的情况再次进行优化，把矩阵转置一下，并交换n和m，再进行上述的操作
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 5000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, m;
int main(){
io;
cin>>n>>m;
if(n > m){//要进行矩阵转置
vector<vector<int>>a(n + 1, vector<int>(m + 1));
vector<vector<int>>sum(m + 1, vector<int>(n + 1));
for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)cin>>a[i][j];
vector<vector<int>>tr(m + 1, vector<int>(n + 1));
for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)tr[i][j] = a[j][i];
swap(n, m);
for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)sum[i][j] = sum[i - 1][j] + tr[i][j];//对每一列都求前缀和
ll ans = -inf;
for(int i = 1; i <= n; ++i){
for(int j = i; j <= n; ++j){
ll cnt = 0;
for(int k = 1; k <= m; ++k){
//这里的0ll相当于一个为值为0的变量，如果cnt小于0，就说明前面选的连续的几个大和已经小于0了，是负数，不管自己是不是负数，自己加上一个负数肯定是比原来小，所以加了这个负数还不如不加，就加0，这里就很类似于求连续的最大子串dp
cnt = max(cnt, 0ll) + sum[j][k] - sum[i - 1][k];
ans = max(ans, cnt);//实时跟新答案
}
}
}
cout<<ans<<endl;
}
else{//同上，只不过没有转置操作了
vector<vector<int>>tr(n + 1, vector<int>(m + 1));
vector<vector<int>>sum(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)cin>>tr[i][j];
for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)sum[i][j] = sum[i - 1][j] + tr[i][j];
ll ans = -inf;
for(int i = 1; i <= n; ++i){
for(int j = i; j <= n; ++j){
ll cnt = 0;
for(int k = 1; k <= m; ++k){
cnt = max(cnt, 0ll) + sum[j][k] - sum[i - 1][k];
ans = max(ans, cnt);
}
}
}
cout<<ans<<endl;
}
return 0;
}
友谊纽带
题意：
小航是计算机系的学生，但他并不喜欢自己的专业。在课余时间，小航喜欢研究社会学的内容，在他经过了多年的研究后，他发现了一个伟大的定理：世界上任意两个人之间最少需要k个友谊纽带就可以全部连接。他需要向世界公布这个研究成果，但是他还没有对这个定理进行验证，由于他急着陪女朋友，所以将验证这个定理的任务交给了他的朋友小杰和小坤。
由于人数太多，而导致任务量非常大，所以小杰和小坤找到了你，请你帮助他们验证这个结论。
思路：
又是一个会错题意的题(╥﹏╥)，比赛的时候以为是找到一个最短的路，使得所有的点连在一起，那么我就直接用并查集判掉，如果存在的话就相当于一颗最小生成树，输出n-1即可
但是！题意是：任意两个人之间都有路能到，并求出最远的两个人之间的路有多长
也就是多源最长路？
我用的是n次迪杰斯特拉，每次都判断有没有点到不了，然后更新最大值
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 5000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, m, a, b, tot;
int dist[MAX];
int head[MAX];
bool vis[MAX];
int ans;
struct ran{
int to, next, val;
inline bool operator < (const ran &x)const{
return val > x.val;
}
}tr[MAX];
priority_queue<ran>q;
ran now, nextt;
void built(int u, int v){
tr[++tot].to = v;
tr[tot].next = head[u];
tr[tot].val = 1;
head[u] = tot;
}
int dijkstra(int s){
mem(dist, inf);
mem(vis, 0);
dist[s] = 0;
// vis[s] = 1;
now.to = s;
now.val = 0;
q.push(now);
while (!q.empty()) {
now = q.top();q.pop();
if(vis[now.to])continue;
vis[now.to] = 1;
for(int i = head[now.to]; i != -1; i = tr[i].next){
int u = tr[i].to;
if(dist[u] > tr[i].val + dist[now.to]){
dist[u] = tr[i].val + dist[now.to];
nextt.to = u;
nextt.val = dist[u];
q.push(nextt);
}
}
}
ans = 0;
for(int i = 1; i <= n; ++i){
ans = max(ans, dist[i]);
}
if(ans == inf ) return -1;
else return ans;
}
int main(){
io;
cin>>n>>m;
mem(head, -1);
mem(tr, 0);
int maxn = 0;
for(int i = 1; i <= m; ++i){
cin>>a>>b;
built(a, b);
built(b, a);
}
for(int i = 1; i <= n; ++i){
int k = dijkstra(i);
if(k == -1){
cout<<-1<<endl;
return 0;
}
else {
maxn = max(maxn, k);
}
}
cout<<maxn<<endl;
return 0;
}
传送门
题意：
公元2200年科学家发明了点对点传送门，随后基建狂魔发挥了优良传统，在城市之间进行了大规模建设。
现在你接到了一个任务，上级给你发了一份资料，这份资料是XX地区的传送门建设规划资料，共M条。
领导要求你完成这些任务，使得这个地区的N座城市可以互相传送，你比较喜欢摸鱼，于是你想知道完成任务的最短时间。如果无法完成任务，则输出-1。
注意:A市与B市可以利用C市中转，可以算互相传送。只要达到N座城市可以互相传送的目的就可以，所以规划资料不一定全部建设。
思路：
最小生成树的板子题
用Kruskal算法按照权值从小到大排序，得到一颗生成树时，此时的权值是完成所有任务的时间最小值。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
//#define mod 1000000007
//const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, m, a, b, c, ans, cnt;
int fa[MAX];
struct ran{
int x, y, val;
}tr[MAX];
bool cmp(ran a, ran b){
return a.val < b.val;
}
void init(){
cnt = 0;
mem(tr, 0);
ans = 0;
for(int i = 1; i <= n; ++i)fa[i] = i;
}
int findd(int x){
return x == fa[x] ? x : fa[x] = findd(fa[x]);
}
void emerge(int x, int y){
fa[findd(x)] = findd(y);
}
int main(){
io;
cin>>n>>m;
init();
for(int i = 1; i <= m; ++i){
cin>>tr[i].x>>tr[i].y>>tr[i].val;
}
sort(tr + 1, tr + 1 + m, cmp);
for(int i = 1; i <= m; ++i){
if(findd(tr[i].x) != findd(tr[i].y)){
// ans += tr[i].val;
++cnt;
emerge(tr[i].x, tr[i].y);
if(cnt == n - 1){
cout<<tr[i].val<<endl;
return 0;
}
}
}
cout<<-1<<endl;
return 0;
}
真不愧是暴力杯（bushi
携程公司氛围 85人发布
