CCF CSP 2017·03
做了一段时间的CCF CSP试题，个人感觉是这样分布的
- A、B题基本纯暴力可满分
- B题留心数据范围
- C题是个大模拟，留心即可
- D题更倾向于图论？（个人做到的D题基本都是图论）
- E题就是神仙打架了
A：分蛋糕
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define dd(x) cout<<#x<<'='<<x<<", "
#define de(x) cout<<#x<<'='<<x<<endl
typedef long long ll;
const int maxn = 1e5+5;
int num[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
rep(i,1,n+1) num[i] = i;
while(m--)
{
int p,q;
scanf("%d%d",&p,&q);
int pos = 1;
while(num[pos]!=p) pos++;
if(q>0){
for(int i=pos;i<pos+q;i++) num[i] = num[i+1];
num[pos+q] = p;
}
else{
for(int i=pos;i>pos+q;i--) num[i] = num[i-1];
num[pos+q] = p;
}
}
rep(i,1,n+1) printf("%d%c",num[i],i==n?'\n':' ');
}
B：学生排队
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define dd(x) cout<<#x<<'='<<x<<", "
#define de(x) cout<<#x<<'='<<x<<endl
typedef long long ll;
const int maxn = 1e5+5;
int num[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
rep(i,1,n+1) num[i] = i;
while(m--)
{
int p,q;
scanf("%d%d",&p,&q);
int pos = 1;
while(num[pos]!=p) pos++;
if(q>0){
for(int i=pos;i<pos+q;i++) num[i] = num[i+1];
num[pos+q] = p;
}
else{
for(int i=pos;i>pos+q;i--) num[i] = num[i-1];
num[pos+q] = p;
}
}
rep(i,1,n+1) printf("%d%c",num[i],i==n?'\n':' ');
}
C：Markdown
- 段落之间分情况处理
- 段内采用递归式处理（同一行写了好长，不好看...）
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define dd(x) cout<<#x<<'='<<x<<", "
#define de(x) cout<<#x<<'='<<x<<endl
typedef long long ll;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
void open(){freopen("data.txt", "r", stdin);}
// 单独处理每一行
string format_line(string str)
{
int len = str.size();
string res;
rep(i,0,len){
// 处理强调
if(str[i]=='_'){
int j = i+1;
while(str[j]!='_') j++;
// 递归处理
res = str.substr(0, i).append("<em>").append(format_line(str.substr(i+1, j-i-1))).append("</em>").append(format_line(str.substr(j+1, len-j-1)));
return res;
}
// 处理超链接
else if(str[i]=='['){
int j = i+1;
while(str[j]!=']') j++;
int p = j+1;
int q = p+1;
while(str[q]!=')') q++;
// 递归处理
res = str.substr(0, i).append("<a href=\"").append(format_line(str.substr(p+1, q-p-1))).append("\">").append(format_line(str.substr(i+1, j-i-1))).append("</a>").append(format_line(str.substr(q+1, len-q-1)));
return res;
}
}
return str;
}
// 处理#打头的行
void func_comment(string line)
{
int len = line.size();
int cnt = 0;
int p = 0;
while(line[p]=='#' && p<len){
cnt++;
p++;
}
while(line[p]==' ' && p<len) p++;
cout<<"<h"<<cnt<<">"<<format_line(line.substr(p, len-p))<<"</h"<<cnt<<">"<<endl;
// 寻找第一个不是空格的位置
}
// 处理*打头的行
void func_star(string line)
{
int len = line.size();
int p = 0;
while(line[p]==' ' || line[p]=='*') p++;
cout<<"<li>"<<format_line(line.substr(p,len-p))<<"</li>"<<endl;
}
int main()
{
//open();
string line;
while(getline(cin, line))
{
bool newp = true;
bool newlist = true;
if(line.size()==0){
//puts("00000");
continue;
}
else if(line[0]=='#'){
//puts("######");
func_comment(line);
}
else if(line[0]=='*'){
//puts("*******");
puts("<ul>");
func_star(line);
// 连续不断输入 直到处理完无序列表
while(getline(cin, line))
{
if(line.size()>0 && line[0]=='*') func_star(line);
else break;
}
puts("</ul>");
}
else{
//puts("ppppppppp");
cout<<"<p>";
cout<<format_line(line);
bool flag = false;
while(getline(cin, line)){
if(line.size()==0){
flag = true;
cout<<"</p>"<<endl;
break;
}
cout<<endl;
cout<<format_line(line);
}
if(!flag) cout<<"</p>"<<endl;
}
}
}
D：地铁修建
- 看走了眼本来还以为是个简单的“单源最短路”问题，仔细一看是“最小化路径上的最大值”问题
- 直觉是max()函数拥有和加法一样的单调不减性质（非负数加法），可以直接在单源最短路径问题上修改
- 也就是将
dist[v] = dist[u] + cost变成dist[v] = max(dist[u], cost)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define dd(x) cout<<#x<<'='<<x<<", "
#define de(x) cout<<#x<<'='<<x<<endl
typedef long long ll;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
struct Edge
{
int v;
int cost;
Edge(int _v=0, int _cost=0):v(_v), cost(_cost){}
};
vector<Edge> E[maxn];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[maxn];
int cnt[maxn];
int dist[maxn];
bool SPFA(int start, int n)
{
memset(vis, 0, sizeof(vis));
rep(i,1,n+1) dist[i] = INF;
vis[start] = true;
dist[start] = 0;
queue<int> que;
while(!que.empty()) que.pop();
que.push(start);
cnt[start] = 1;
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = false;
rep(i,0,E[u].size()){
int v = E[u][i].v;
int cost = E[u][i].cost;
// 这里修改了两行
if(dist[v]>max(dist[u],cost)){
dist[v] = max(dist[u], cost);
if(!vis[v]){
vis[v] = true;
que.push(v);
if(++cnt[v]>n) return false;
}
}
}
}
return true;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
SPFA(1,n);
printf("%d\n", dist[n]);
}