竞赛第14期题解
题目不难，但要注意细节。
ps: 由于考试报告下载bug，本帖代码为赛后重新编写。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、网络空间、营销软件、网站建设、
尚志网站维护、网站推广。第一题
题目描述
题目链接
题解
本题题目范围标的是n==x!-1，2<=x<=10，n可以等于0，其实有些矛盾；但只需要注意n=0时返回一个空字符串即可。
#include#include
复杂度分析
时间复杂度为
O
(
n
⋅
x
)
O(n·x)
O(n⋅x)。
其中n为字符串数量，x为字符串长度。
因为数据范围较小，所以可以通过。
第二题
题目描述
已知棋盘大小为n*n。 每个位置都有自己的权值q。 该棋盘中有多少对行权值和小于列权值和。
输入描述：
第一行输入整数n。(1<=n<=100)表示棋盘的大小
以下n行每行输入n个整数表示棋子的权值。(1<=a<=1000)
输出描述：
输出小Q的分值。
输入样例：
3
1 2 3
1 2 3
1 2 3
输出样例：
3
题解
遍历求出每行每列的权值和后遍历比较即可。
#include#includeusing namespace std;
int main() {int n;
cin >>n;
vectorrow(n);
vectorcol(n);
for (int i = 0; i< n; i++) {for (int j = 0; j< n; j++) {int x;
cin >>x;
row[i] += x;
col[j] += x;
}
}
int ans = 0;
for (int i = 0; i< n; i++) {for (int j = 0; j< n; j++) {if (row[i]< col[j]) ans++;
}
}
cout<< ans<< endl;
return 0;
}
复杂度分析
时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
n为棋盘行/列数。
第三题
题目描述
小Q的柠檬汁做完了。 掏出了自己的数字卡牌。 想要和别人做数字游戏。 可是她又不想要输掉游戏。 她制定好规则，每 次每个人只能把这个牌换成它的因子的某个牌。 但是这个因子不能是1或者整数本身。 现在给出整数n。 两个人开始做游 戏，谁无法再给出因子牌则该人胜利，如果该整数无因子牌直接视为先手胜利，请判断先手在最优策略状态下能否必胜。
题解
- 如果该数是质数，则先手胜。
- 如果该数（除1和本身外）只有两个因数，则后手胜。
- 如果该数（除1和本身外）的因数大于等于三个，易证明，先手总可以制造第二种情况，先手胜。
#include#include#includeusing namespace std;
int main() {int n;
cin >>n;
int flag = 0;
int sq = (int)sqrt((double)n);
for (int i = 2; i<= sq; i++) {while(n % i == 0) {n /= i;
flag++;
}
if (flag == 2 && n == 1) {cout<< 2<< endl;
return 0;
}
}
cout<< 1<< endl;
return 0;
}
复杂度分析
时间复杂度为
O
(
n
)
O(\sqrt{n})
O(n
)。
第四题
题目描述
题目链接
题解
这道题还是要先读懂题意，开始误以为题目要求就是26进制转换，后来才发现要求字母按升序排列。并且要注意判断字符串是否满足在字母表中这一要求，若不满足需要输出0！！！
洛谷及各种平台有很多关于数位dp及本题其他解法的题解。下面给出一种数位dp的代码。
#include#include
using namespace std;
char arr[10];
long long ans, sum[30][10];
int num;
int main(void)
{scanf("%s",&arr);
if(strlen(arr) >6){cout<< 0<< endl;
return 0;
}
for(int i = 0; i< strlen(arr); i ++){if(arr[i]< 'a' || arr[i] >'z'){cout<< 0<< endl;
return 0;
}
}
for(int i = 1; i< strlen(arr); i ++){if(arr[i - 1] >= arr[i]){cout<< 0<< endl;
return 0;
}
}
for(int i = 1; i<= 26; i ++) sum[i][1] = 1;
for(int j = 2; j<= 6; j ++){for(int i = 27 - j; i >0; i --){sum[i][j] = sum[i + 1][j - 1] + sum[i + 1][j];
}
}
for(int j = strlen(arr) - 1; j >= 0; j --){num ++;
for(int i = 1; i<= arr[j] - 'a' + 1; i ++){ans += sum[i][num];
}
}
cout<< ans<< endl;
return 0;
}
复杂度分析
时间复杂度为
O
(
C
⋅
n
)
O(C·n)
O(C⋅n)。
其中n为输出单词长度。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页题目：CSDN竞赛第14期题解-创新互联
标题链接：
http://www.cdkjz.cn/article/csijdp.html
