写在前面
CSP（计算机软件能力认证考试），主要覆盖大学计算机专业所学习的程序设计，数据结构，算法以及相关的数学基础知识。
包括但不限于：
-
程序设计基础：
逻辑与数学运算，分支循环，过程调用（递归），字符串操作，文件操作，etc. -
数据结构：
线性表（数组，队列，栈，链表），树（堆，排序二叉树），哈希表，集合与映射，图，etc. -
算法与算法设计策略：
排序与查找，枚举，贪心策略，分治策略，递推与递归，动态规划，搜索，图论算法，计算几何，字符串匹配，线段树，随机算法，近似算法, etc.
考试模式：
-
OI机制（分点给分
-
4h内完成5道题
题型大致分布&注意事项：（据一位CSP420分的学姐说
-
第一题：水题
稍有编程经验，20+-行代码可搓完
1.注意细节：
long long
边界
特殊情况
2.用文件读入可节省大量时间
3.宏定义节省for循环书写用时
#define _for(i , a , b) for(int i=a; i<b; i++)4.声明数组大小时，用const定义的伪常量方便修改const int N=1007 int Num[N] , Sum[N]; char str[N] -
第二题：小模拟
处理比较简单的问题，需要梳理简单的逻辑和过程
1.多重循环，接近n^2的复杂度。一般是时序题，熟练运用排序、多元数组、STL会有奇效
2.必备STL神器
string：字符串查找、拼接、花式读入
set：自动排序，去重
vector：盲开数组的首要选择
priority_queue：自定义优先级的队列
map：不同类型数据的双向字典 -
第三题：大模拟，字符串处理
处理复杂的问题，涉及字符串的问题居多
1.熟练掌握各种输入函数与字符串的处理，DFS, BFS，
2.会设计复杂的层次化结构
3.题库
ZJU：acm.zju.edu.cn
PKU：acm.pku.edu.cn/JudgeOnline
HDU：acm.hdu.edu.cn
USACO：train.usaco.org/usacogate
Codeforces：codeforces.com
4.题目不难，只是变态（?） -
第四题：算法题
难度中，重点考图论和动规
1.熟练掌握最小生成树、最短路径、简单递推
2.会强连通分量，欧拉函数，动规优化（四边形优化，etc.
3.会将DFS转变为非递归式避免爆栈（80‘->100’） -
第五题：算法题
难度高，设计算法面很多，数据量很大，需要堆算法极致优化，很难满分
1.熟练掌握各种程序设计算法，以及对时间、空间的优化
2.快速coding, debug
3.精神状态极佳
骗分建议：
-
贪心
-
搜索+剪枝
-
暴力打表：简单数学分析+猜测找规律
-
分类讨论
-
固定输出
-1.重复局面
分析
用上STL送昏
-
题目有点绕
-
读不懂==刚开始做CSP的正常现象
根据样例，每8行构成一个棋局，采用字符串数组string的数据结构：
-
读入n（代表该盘棋有n步
-
读入每一步的8行局面，每8行合并成一个string串（含64个字符）
-
设置计数器count，default为1
-
for循环与前面每一个string串，比较，相等则count++
-
输出count
AC:
#include<iostream>
#include <string>
using namespace std;
int main(){
int n;
cin>>n;
string chess[110];
for(int i=1;i<=n;i++){ //每盘
for(int j=1;j<=8;j++){ //每行
string temp;
cin>>temp;
chess[i]=chess[i]+temp;
}
int count=1;
for(int k=1;k<i;k++){
if(chess[k]==chess[i])
count++;
}
cout<<count<<endl;
}
return 0;
)
-2矩阵运算
分析
顺序模拟会显示超时（有时候一个人敲代码就挺无助的。。。
-
tmp = Q x KT（此时tmp是nxn大小，会爆
-
tmp = W · tmp
-
ans = tmp x V
-
达咩
所以可以先算后面两个矩阵，这样时间复杂度就可以过了
-
tmp = KT x V（此时是dxd大小，安全
-
ans = Q x tmp
-
（第一遍做的时候还没复习线代，死活没想到这一点
-
两矩阵运算时，会用到三重for循环
-
ijk，一般纸上模拟一遍就有思路了
测试数据：
3 2
1 2
3 4
5 6
10 10
-20 -20
30 30
6 5
4 3
2 1
4 0 -5
UNAC：k是矩阵叉乘的内标
-
超时超内存
-
限制5s, 512MB
-
这串码5.062s, 771.3MB
#include<bits/stdc++.h>
using namespace std;
int n,d;
const int N=10010,D=30;
int Q[N][D],K[N][D],V[N][D],W[N];
long long tmp[D][D],ans[N][N];
int main(){
cin>>n>>d;
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
cin>>Q[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
cin>>K[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
cin>>V[i][j];
for(int i=1;i<=n;i++) cin>>W[i];
//tmp=KTxV
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
for(int k=1;k<=n;k++)
tmp[i][j]+=K[k][i]*V[k][j];
//tmp[i][j]+=K[k][j]*V[k][j];戳辣
//在列的位置，但是有i个
//ans=Qxtmp
//ans*=W
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++){
for(int k=1;k<=n;k++) //这里错了k=d
ans[i][j]+=Q[i][k]*tmp[k][j];
ans[i][j]*=W[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=d;j++)
cout<<ans[i][j]<<' ';
cout<<endl;
}
return 0;
}
AC：
#include<bits/stdc++.h>
using namespace std;
const int N=10010,D=30;
long long tmp[D][D],ans[N][N];
int n,d;
int Q[N][D],K[N][D],V[N][D],W[N];
int main(){
cin>>n>>d;
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
cin>>Q[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
cin>>K[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
cin>>V[i][j];
for(int i=1;i<=n;i++) cin>>W[i];
//tmp=KTxV
for(int i=1;i<=n;i++)
for(int j=1;j<=d;j++)
for(int k=1;k<=n;k++)
tmp[i][j]+=K[k][i]*V[k][j];
//ans=Qxtmp
//ans*=W
for(int i=1;i<=n;i++){
for(int j=1;j<=d;j++){
for(int k=1;k<=d;k++) //for(int k=1;k<=n;k++)
ans[i][j]+=Q[i][k]*tmp[k][j];
ans[i][j]*=W[i];
cout<<ans[i][j]<<' ';
}
cout<<endl;
}
return 0;
}