【入门1】顺序结构
P1008 [NOIP1998 普及组] 三连击
https://www.luogu.com.cn/problem/P1008
模拟，枚举所有可能的a，输出满足条件的a，b，c。
#include <bits/stdc++.h>
using namespace std;
int main(){
int v;
bool a[10];//ai表示第i个数已经用过了
for(int i = 123; i < 329; i++){
memset(a, 0, sizeof(a));
v = 0;
a[i % 10] = a[i / 10 % 10] = a[i / 100] = 1;
a[i * 2 % 10] = a[i * 2 / 10 % 10] = a[i * 2 / 100] = 1;
a[i * 3 % 10] = a[i * 3 / 10 % 10] = a[i * 3 / 100] = 1;//统计数字
for(int j = 1; j <= 9; j++) v += a[j]; //v表示1-9这些数字是否全部齐了
if(v == 9) printf("%d %d %d\n", i, i * 2, i * 3);//如果齐了就输出
}
return 0;
}【入门2】分支结构
P5717 【深基3.习8】三角形分类
https://www.luogu.com.cn/problem/P5717
在一个三角形中，如果较短的两条边的平方和大于最长边的平方，那么这个三角形是锐角三角形，否则它是钝角三角形。
if(a[0] * a[0] + a[1] * a[1] > a[2] * a[2]) printf("Acute triangle\n");
if(a[0] * a[0] + a[1] * a[1] < a[2] * a[2]) printf("Obtuse triangle\n"); 【入门3】循环结构
P1009 [NOIP1998 普及组] 阶乘之和
https://www.luogu.com.cn/problem/P1009
50！非常大，需要用高精度数。
这里编译要用c++11，不然用c++会报错"错误：在 C++98 中‘sum’必须由构造函数而不是‘{...}’初始化
vector<int> sum = {0};"</int>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
vector<int> add(vector<int> &A, vector<int> &B){
if(A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for(int i = 0; i < A.size(); i++){
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if(t > 0) C.push_back(t);
return C;
}
vector<int> mul(vector<int> &A, int b){
vector<int> C;
int t = 0;
for(int i = 0; i < A.size() || t; i++){
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main(){
int n;
cin >> n;
vector<int> sum = {0};
vector<int> t = {1};
for(int i = 1; i <= n; i++){
t = mul(t, i);
sum = add(sum, t);
}
for(int i = sum.size() - 1; i >= 0; i--) printf("%d", sum[i]);
return 0;
}P1217 [USACO1.5]回文质数 Prime Palindromes
https://www.luogu.com.cn/problem/P1217
1.偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000。2.偶数肯定不是质数。这样至少排除一半多的数据量。3，你回文数已经判断出来了，在此中判断即可。
#include <bits/stdc++.h>
using namespace std;
bool is_hw(int x){
int tmp = x, reverse = 0;
while(tmp){
reverse = reverse * 10 + tmp % 10;
tmp /= 10;
}
return x == reverse;
}
bool is_prime(int x){
for(int i = 2; i <= x / i; i++){
if(x % i == 0) return false;
}
return true;
}
int main(){
int a, b;
cin >> a >> b;
if(a % 2 == 0) a++; //偶数一定不是质数
for(int i = a; i <= b; i += 2){
if(i > 10000000) break;
if(is_hw(i)){
if(is_prime(i)) cout << i << endl;
}
}
return 0;
}【入门4】数组
P5731 【深基5.习6】蛇形方阵
https://www.luogu.com.cn/problem/P5731
注意每个数字有都会占用 3 个字符，前面使用空格补齐。
用 printf("%3d",a[i][j]);
%3d 表示输出3位整型数, 不够3位右对齐。%2d 表示输出2位整型数, 不够2位右对齐。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
int a[N][N];
//绕着走的四个方向，右、下、左、上（要按顺序）
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
定义一个改变位置的数组，还有一个变量记录现在头朝哪边。如果越界或以前填过，就改变方向。
int main(){
int n;
cin >> n;
int x = 1, y = 1, d = 0;
for(int i = 1; i <= n * n; i++){
a[x][y] = i;
int tx = x + dir[d][0], ty = y + dir[d][1];
if(tx < 1 || tx > n || ty < 1 || ty > n || a[tx][ty] != 0)
d = (d + 1) % 4;
x = x + dir[d][0], y = y + dir[d][1];
}
for(int i = 1; i <= n; i++){//按题意输出
for(int j = 1; j <= n; j++){
printf("%3d", a[i][j]);
}
cout << endl;
}
//printf("%d\n", key);
return 0;
}P1205 [USACO1.2]方块转换 Transformations
https://www.luogu.com.cn/problem/P1205
是比较复杂的模拟，需要仔细考虑，不要粗心写错了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
struct Matrix{
int map[12][12];
int n;
}from, to;
//Right 90
bool t1(const Matrix& in){
for(int i=1;i<=in.n;i++){
for(int j=1;j<=in.n;j++){
if(in.map[i][j]!=to.map[j][in.n-i+1]) return 0;
}
}
return 1;
}
//Right 180
bool t2(const Matrix& in){
for(int i=1;i<=in.n;i++){
for(int j=1;j<=in.n;j++){
if(in.map[i][j]!=to.map[in.n-i+1][in.n-j+1]) return 0;
}
}
return 1;
}
//Right 270
bool t3(const Matrix& in){
for(int i=1;i<=in.n;i++){
for(int j=1;j<=in.n;j++){
if(in.map[i][j]!=to.map[in.n-j+1][i]) return 0;
}
}
return 1;
}
//Reflect
bool t4(const Matrix& in){
for(int i=1;i<=in.n;i++){
for(int j=1;j<=in.n;j++){
if(in.map[i][j]!=to.map[i][in.n-j+1]) return 0;
}
}
return 1;
}
bool t5(const Matrix& in){
Matrix tmp;tmp.n=in.n;
for(int i=1;i<=in.n;i++){
for(int j=1;j<=in.n;j++){
tmp.map[i][j]=in.map[i][in.n-j+1];
}
}
return (t1(tmp)||t2(tmp)||t3(tmp));
}
bool t6(const Matrix& in){
for(int i=1;i<=in.n;i++){
for(int j=1;j<in.n;j++){
if(in.map[i][j]!=to.map[i][j]) return 0;
}
}
return 1;
}
int main(){
scanf("%d",&from.n); to.n=from.n;
string tmp;
getline(cin,tmp);
for(int i=1;i<=from.n;i++){
getline(cin,tmp);
for(int j=0;j<from.n;j++) from.map[i][j+1]=tmp[j];
}
for(int i=1;i<=to.n;i++){
getline(cin,tmp);
for(int j=0;j<to.n;j++) to.map[i][j+1]=tmp[j];
}
if(t1(from) == 1){
printf("1");
exit(0);
}
if(t2(from) == 1){
printf("2");
exit(0);
}
if(t3(from) == 1){
printf("3");
exit(0);
}
if(t4(from) == 1){
printf("4");
exit(0);
}
if(t5(from) == 1){
printf("5");
exit(0);
}
if(t6(from) == 1){
printf("6");
exit(0);
}
printf("7");
return 0;
}【入门5】字符串
#include <cctype>
这是一个拥有许多字符串处理函数声明的头文件，这些函数可以用来对单独字符串进行分类和转换；
例如：
isalpha():检查这个字符是否为字母，真返回1，假返回0；
isalnum()：检查这个字符是否为字母或数字数字，同上；
isdigit():检查这个字符是否为十进制数字，同上；
islower():检查这个字符是否为小写字母，同上；
字符串操作
https://www.cnblogs.com/komean/p/11109555.html
https://www.luogu.com.cn/problem/P1308
P1308 [NOIP2011 普及组] 统计单词数
https://www.luogu.com.cn/problem/solution/P1308
注意有可能以空格开头!
改了好久终于没有bug了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
string to_lower(string s){
for(int i = 0; i < s.size(); i++)
if(isupper(s[i])) s[i] = s[i] - 'A' + 'a';
return s;
}
int main(){
int ans = 0, pos = -1;
bool flag = false;//判断是否找到
string w, s;
getline(cin, w);
w = to_lower(w);
getline(cin, s);
if(s[s.length() - 1] != ' ') s += ' ';
int p = 0;
string tmp = "";
while(p < s.size()){
if(s[p] != ' ') {
if(isupper(s[p])) s[p] = s[p] - 'A' + 'a';
tmp += s[p];
p++;
}
else{
if(tmp == w){
ans++;
if(flag == false){
flag = true;
pos = p - tmp.size();
}
}
tmp = "";
p++;
}
}
if(flag) printf("%d %d\n", ans, pos);
else printf("%d\n", pos);
return 0;
}P1603 斯诺登的密码
https://www.luogu.com.cn/problem/P1200
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
char dic[30][20]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty","a","both","another","first","second","third"};
int di[30]={0,1,4,9,16,25,36,49,64,81,00,21,44,69,96,25,56,89,24,61,0,1,4,1,1,4,9};
char s[100];
unsigned long long int a[10], top, flag;
int main(){
for(int i = 0; i < 6; i++){
cin >> s;
for(int j = 1; j <= 26; j++){
if(!strcmp(s, dic[j])){
a[++top] = di[j];
break;
}
}
}
sort(a + 1, a + top + 1);
for(int i = 1; i <= top; i++){
if(flag){
printf("%.2d", a[i]);
}
else{
if(a[i]){
printf("%d",a[i]);
flag = 1;
}
}
}
if(!flag) printf("0");
//printf("%d\n%d\n", boy, girl);
return 0;
}【入门6】函数与结构体
P1304 哥德巴赫猜想
https://www.luogu.com.cn/problem/P1304
自己很快写出来的，记录一下
#include <bits/stdc++.h>
using namespace std;
typedef pair<string, string> PSS;
const int N = 10010;
int prime[N], cnt;
int st[N];
void get_prime(){
for(int i = 2; i <= N; i++){
if(!st[i]) prime[cnt++] = i;
for(int j = 0; prime[j] <= N / i; j++){
st[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
}
int main(){
int n;
cin >> n;
get_prime();
for(int i = 4; i <= n; i += 2) {
for(int j = 0; j < cnt; j++){
if(st[i - prime[j]] == 0){
cout << i << "=" << prime[j] << "+" << i - prime[j] << endl;
break;
}
}
}
//printf("%d\n", cnt);
return 0;
}P2415 集合求和
https://www.luogu.com.cn/problem/P2415
涉及排列组合计算。
京公网安备 11010502036488号