骗分与NOIP技巧 代码仓库
Sweetlemon
2018-10-31 14:49:51
## 例题 代码
### 魔法阵 $10$分
```cpp
#include <iostream>
using namespace std;
int main(void){
int n,m;
cin >> n >> m;
for (int i=0;i<m;i++)
cout << "0 0 0 0\n";
return 0;
}
```
### 小凯的疑惑 $30$分
```cpp
#include <iostream>
using namespace std;
int ok[10005]; //ok是标记数组，ok[i]==1表示金额i可以支付；数组开得比范围略大
int inf=10000; //假设不能支付的金额不会超过10000元
int max_coins=100; //假设每一种硬币支付的金额不会超过100枚
int main(void){
int a,b;
int ans=1; //1一定无法支付，否则没有答案
cin >> a >> b;
//枚举a,b两种硬币支付的数目
for (int i=0;i<=max_coins;i++) //支付a硬币数量
for (int j=0;j<=max_coins;j++) //支付b硬币数量
ok[a*i+b*j]=1; //支付i枚a硬币和j枚b硬币，是可以做到的
for (int i=0;i<=a*max_coins;i++)
if (ok[i]==0) //表明i不能被支付
ans=i; //由于i是从小到大枚举的，因此i就是当前不能支付的最大金额
cout << ans << endl;
return 0;
}
```
### 列队 $30$分
```cpp
#include <cstdio>
using namespace std;
int cube[1005][1005]; //记录每个位置上人的编号
int main(void){
int n,m,q; //n行, m列, q次查询
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cube[i][j]=(i-1)*m+j; //计算初始时每个人的编号
for (int i=0;i<q;i++){
int x,y,now; //(x,y)表示当前离队的人所在的行、列，now表示当前离队的人的编号
scanf("%d%d",&x,&y);
now=cube[x][y];
printf("%d\n",now);
//向左看齐
for (int j=y;j<m;j++)
cube[x][j]=cube[x][j+1]; //把y右边的人向左移动一个位置
//向前看齐
for (int j=x;j<n;j++)
cube[j][m]=cube[j+1][m]; //把x下面的、位于第m列的人向前移动一个位置
cube[n][m]=now; //离队的人回到第n行第m列
}
return 0;
}
```
### 写文件 示例（提交到洛谷上会WA）
```cpp
#include <cstdio>
using namespace std;
int main(void){
freopen("apb.in","r",stdin);
freopen("apb.out","w",stdout);
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
return 0;
}
```
### 天天爱跑步 $20$分
```cpp
#include <iostream>
using namespace std;
int w[1005]; //每个节点观察员的出现时间
int cnt[1005]; //每个节点观察员能够观察到的玩家数量
int main(void){
int n,m; //观察员的数量和玩家的数量
cin >> n >> m;
for (int i=1;i<=n-1;i++){
int u,v;
cin >> u >> v; //这个输入没用（骗分用不到）
}
for (int i=1;i<=n;i++)
cin >> w[i]; //读入观察员出现的时间
for (int i=1;i<=m;i++){
int s,t;
cin >> s >> t; //读入玩家的起点和终点
if (w[s]==0) //检查起点的观察员出现的时间是否为0
cnt[s]++; //如果为0，这个观察员能够观察到的玩家数目+1
}
for (int i=1;i<=n;i++)
cout << cnt[i] << ' ';
return 0;
}
```
## 练习 代码
### 棋盘 $5$分
考虑可能的无解情况。
```cpp
#include <iostream>
using namespace std;
int main(void){
cout << "-1\n";
return 0;
}
```
### 魔法阵 $40$分
```cpp
#include <cstdio>
using namespace std;
int x[40005]; //魔法值
int a[40005],b[40005],c[40005],d[40005];
//分别作为A,B,C,D物品出现的次数
int main(void){
int n,m;
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++)
scanf("%d",x+i); //这个读入方法初赛考过，相当于scanf("%d",&a[i]);
for (int i=0;i<m;i++){
for (int j=0;j<m;j++){
if (i==j)
continue; //一个物品不能同时作为A物品和B物品
for (int k=0;k<m;k++){
if (k==i || k==j)
continue; //同理
for (int l=0;l<m;l++){
if (l==i || l==j || l==k)
continue; //同理
//判断能否组成魔法阵
if (x[i]<x[j] && x[j]<x[k] && x[k]<x[l]
&& (x[j]-x[i])==2*(x[l]-x[k])
&& (x[j]-x[i])*3<x[k]-x[j]){
//可以组成魔法阵，更新出现次数
a[i]++;
b[j]++;
c[k]++;
d[l]++;
}
}
}
}
}
//输出
for (int i=0;i<m;i++)
printf("%d %d %d %d\n",a[i],b[i],c[i],d[i]);
return 0;
}
```
事实上，上面的代码可以进行简单优化，优化后可以多得$15$分。
优化的方法很简单：把判断尽可能提前，避免枚举一些不可能组成魔法阵的组合方式。
这种技巧我们称作“剪枝”，在做更难的题目的时候非常有用。
```cpp
#include <cstdio>
using namespace std;
int x[40005];
int a[40005],b[40005],c[40005],d[40005];
int main(void){
int n,m;
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++)
scanf("%d",x+i);
for (int i=0;i<m;i++){
for (int j=0;j<m;j++){
if (i==j || x[i]>=x[j]) //x[i]>=x[j]则不可能组成魔法阵
continue;
for (int k=0;k<m;k++){
if (k==i || k==j || x[j]>=x[k] ||
(x[j]-x[i])*3>=(x[k]-x[j]))
//x[j]-x[i]*3>=x[k]-x[j]则不可能组成魔法阵
continue;
for (int l=0;l<m;l++){
if (l==i || l==j || l==k || x[k]>=x[l])
continue;
if ((x[j]-x[i])==2*(x[l]-x[k])){
a[i]++;
b[j]++;
c[k]++;
d[l]++;
}
}
}
}
}
for (int i=0;i<m;i++)
printf("%d %d %d %d\n",a[i],b[i],c[i],d[i]);
return 0;
}
```
### 转圈游戏 $30$分
这题实际上是数学题，但这里我们采用暴力模拟的方法。
```cpp
#include <iostream>
using namespace std;
int main(void){
int n,m,x,k; //n个小伙伴，每次走m步，需要求的是x号小伙伴的位置，进行10^k轮
long long ans; //ans保存x号小伙伴的位置
long long turns=1; //turns计算游戏进行的轮数
cin >> n >> m >> k >> x;
for (int i=1;i<=k;i++)
turns=turns*10; //令turns=10^k
ans=x; //游戏开始前在x号位置
for (int i=1;i<=turns;i++){
ans+=m; //移动m个位置
if (ans>=n) //ans>=n表示已经绕了一圈（注意位置从0开始编号）
ans-=n;
}
cout << ans << endl;
return 0;
}
```
### 线索 $40$分
这题实际上是数据结构题，这里我们也采用暴力模拟。
```cpp
#include <iostream>
#include <algorithm>
#define MAXN 5005
using namespace std;
int color[5005]; //记录每条丝线的颜色
int temp_arr[5005]; //临时数组
int connect[5005][5005]={0}; //记录与每个点建立联系的点
int connect_num[5005]={0}; //记录与每个点建立联系的点的数量
int main(void){
int n,m; //n条丝线,m次操作
cin >> n >> m;
for (int i=1;i<=n;i++)
cin >> color[i]; //输入初始颜色
for (int i=0;i<m;i++){
int a,l,r,x;
cin >> a >> l >> r >> x;
switch (a){
case 1:
//把从l到r的丝线以及与这些丝线建立联系的所有丝线染成颜色x
for (int j=l;j<=r;j++){ //枚举区间内所有丝线
color[j]=x; //先把丝线本身染成x色
for (int k=0;k<connect_num[j];k++) //枚举与它建立联系的所有丝线connect[j][k]
color[connect[j][k]]=x; //染色
}
break;
case 2:
int is_connected=0; //记录l和r是否已经建立联系
color[l]=color[r]=x; //先对l,r进行染色
for (int k=0;k<connect_num[l];k++){
if (connect[l][k]==r){ //已经建立联系
is_connected=1;
break;
}
}
if (is_connected){ //如果已经建立联系，就只需要再染色就好了
for (int k=0;k<connect_num[l];k++) //枚举与l建立联系的所有丝线（也可以枚举与r建立联系的所有丝线）
color[connect[l][k]]=x; //染色
continue;
}
int new_connect_num=0; //记录形成的新的结所含的丝线数目
for (int k=0;k<connect_num[l];k++){
temp_arr[new_connect_num]=connect[l][k]; //把与l建立联系的丝线放进临时数组
new_connect_num++; //更新形成的新的结所含的丝线数目
}
for (int k=0;k<connect_num[r];k++){
temp_arr[new_connect_num]=connect[r][k]; //把与r建立联系的丝线放进临时数组
new_connect_num++; //更新形成的新的结所含的丝线数目
}
//再把l和r放进临时数组，并更新丝线数目
temp_arr[new_connect_num]=l;
new_connect_num++;
temp_arr[new_connect_num]=r;
new_connect_num++;
//对新的结中所有丝线进行染色，并更新与之建立联系的丝线数组(connect数组)和丝线数目(connect_num数组)
for (int j=0;j<new_connect_num;j++){
int now_process=temp_arr[j]; //记录当前处理的丝线编号
connect_num[now_process]=new_connect_num-1; //注意，减去1是因为丝线不能和自己建立联系
color[now_process]=x; //染色
int k=0; //k记录数组connect的下标
for (int t=0;t<new_connect_num;t++){
if (t==j) //不能把自己放进联系数组中
continue;
connect[now_process][k]=temp_arr[t]; //把temp_arr[t]放入联系数组
k++; //移动到下一个位置
}
}
break;
}
}
//输出每条丝线的颜色和与之建立联系的丝线数量
for (int i=1;i<=n;i++)
cout << color[i] << ' ';
cout << endl;
for (int i=1;i<=n;i++){
cout << connect_num[i] << ' ';
}
cout << endl;
return 0;
}
```
### 日常 $5$分
这题实际上是数学题。
直接输出所有盘子按顺序排列的方案。
```cpp
#include <iostream>
#define MOD 993244853
using namespace std;
int main(void){
int n;
int c0;
cin >> n >> c0;
cout << c0%MOD << endl;
for (int i=1;i<=n;i++)
cout << i << ' ';
return 0;
}
```
### 日常 $20$分
通过$\text{dfs}$，枚举所有摆盘子的方法，统计每个错乱数对应的摆法数；找到最优答案后，再$\text{dfs}$一次找到字典序最小的方案。
### 探访 $5$分
这题实际上是图论题。
~~有一点点~~太难了呢。
在图上进行$\text{dfs}$寻找最优方案。
```cpp
#include <iostream>
#include <algorithm>
#include <vector> //这个是vector（可以理解为变长数组）
#define MAXN 10005
#define INF 100000000000000ll
using namespace std;
struct Edge{
int u,v,w,k;
Edge(void):u(0),v(0),w(0),k(0){}
Edge(int tu,int tv,int tw,int tk):u(tu),v(tv),w(tw),k(tk){}
Edge(const Edge &te):u(te.u),v(te.v),w(te.w),k(te.k){}
}; //边结构体
vector<Edge> g[MAXN];
int vis[MAXN]={0}; //记录某个点是否走过
typedef vector<Edge>::iterator iter; //迭代器（严重超纲）
int n;
int maxk,dis; //记录当前走过的路径的k的最大值和路径总长度
long long ans=INF;
void dfs(int x);
int main(void){
int m;
cin >> n >> m;
for (int i=0;i<m;i++){
int u,v,w,k;
cin >> u >> v >> w >> k;
g[u].push_back(Edge(u,v,w,k)); //这个是存图的方法（vector邻接表）
}
maxk=dis=0;
dfs(1); //从1号节点开始枚举路径找答案
cout << ans << endl;
return 0;
}
void dfs(int x){
if (x==n){ // 如果已经到达了n号节点
if ((long long)(maxk)*dis<ans) //更新答案
ans=(long long)(maxk)*dis;
return;
}
for (iter it=g[x].begin();it!=g[x].end();it++){
if (!vis[it->v]){
//枚举从x节点出发的每一条边
//如果这条边的到达点没有被访问过，就访问它
vis[it->v]=1;
dis+=it->w; //更新距离
int tmx=maxk; //保存原来的maxk，便于恢复
if ((it->k)>maxk)
maxk=it->k; //更新maxk
dfs(it->v); //dfs访问
maxk=tmx; //恢复原来的maxk
dis-=it->w; //恢复dis变量的值
vis[it->v]=0; //恢复vis数组
}
}
}
```
### 绝美的挣扎 $10$分
这题实际上是动态规划（$\text{dp}$）题。
考虑$k_i=0$的情况。此时所有设施彼此不会互相影响，可以控制所有设施，所以答案为所有设施的重要度之和。
```cpp
#include <iostream>
using namespace std;
int w[1005];
int main(void){
int n;
int ans=0;
cin >> n;
for (int i=0;i<n;i++){
cin >> w[i];
ans+=w[i];
}
cout << ans << endl;
return 0;
}
```
### 绝美的挣扎 $20$分
考虑$n\le 20$的情况，直接进行暴搜。再加上上面的$10$分，一共可以得到$20$分。
这种在一个程序里根据数据的特点、写两种不同做法的方法，叫做按数据分治。按数据分治是很重要的得分方法！
另外，下面的程序也可以进行剪枝优化，你知道怎么做吗？
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int maxans=0;
int ans=0;
int w[1005],k[1005];
int chose[1005]={0}; //记录方案，表示是否控制这个设施
void dfs(int x);
int chk(void); //检查这种方案是否可行
int main(void){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",w+i);
for (int i=1;i<=n;i++)
scanf("%d",k+i);
int special=1; //special=1表示所有k等于0的特殊情况
for (int i=1;i<=n;i++){
if (k[i]>0){
special=0;
break;
}
}
if (special){ //特殊情况直接求和
for (int i=1;i<=n;i++)
maxans+=w[i];
printf("%d\n",maxans);
return 0;
}
//否则爆搜
dfs(1);
printf("%d",maxans);
return 0;
}
int chk(void){
for (int i=1;i<=n;i++){
if (!chose[i])
continue;
//枚举所有i可能影响到的设施
//注意是环形，要处理下标
for (int j=i-k[i];j<=i+k[i];j++){
int tj=j; //不要对循环变量进行操作，否则可能导致死循环
if (tj<=0) //小于0表示转回头了，要+n
tj+=n;
else
if (tj>n) //大于n表示转了一圈，要-n
tj-=n;
if (tj!=i && chose[tj]) //如果选择了干扰范围内的另一个设施，说明该方案不可行
return 0;
}
}
//方案可行
return 1;
}
void dfs(int x){
if (x>n){
//已经枚举完毕
if (chk()) //如果方案合法
maxans=max(maxans,ans); //更新答案
return;
}
//不选x号设施
dfs(x+1);
//选择x号设施
chose[x]=1,ans+=w[x];
dfs(x+1);
chose[x]=0,ans-=w[x]; //记得还原哦
}
```