CCF 2014-03
CCF 历年题目集
A. 相反数
用map进行计算。
#include
#include B. 窗口
模拟
#include
using namespace std;
struct Window {
int x1,y1,x2,y2,id;
}w[20];
int n,m;
int a,b,c,d;
int get(int x,int y)
{
for (int i = n ; i >= 1 ; i -- )
{
if(w[i].x1 <= x && w[i].x2 >= x && w[i].y1 <= y && w[i].y2 >= y) return i;
}
return 0;
}
int main()
{
cin >> n >> m;
for (int i = 1 ; i <= n ; i ++ )
{
cin >> a >> b >> c >> d;
w[i] = {a,b,c,d,i};
}
while(m -- )
{
int x,y;
cin >> x >> y;
int u = get(x,y);
if(u) cout << w[u].id << endl;
else {
cout << "IGNORED" << endl;
continue;
}
w[n+1] = w[u];
for (int i = u ; i <= n ; i ++ ) w[i] = w[i+1];
}
return 0;
}
C. 命令行选项
该题的关键是会用 stringstream 处理输入，之后按照题目要求进行模拟。
#include
using namespace std;
map mp; // 1 带参数，2 不带参数
string ans[30];
int main()
{
string s;
cin >> s;
s += " ";
for (int i = 0 ; i < s.size() ; i ++ )
{
if(s[i] <= 'z' && s[i] >= 'a' && s[i + 1] == ':') mp[s[i]] = 1;
else mp[s[i]] = 2;
}
int n;
cin >> n;
getchar();
for (int k = 1 ; k <= n ; k ++ )
{
cout << "Case " << k << ": ";
getline(cin,s);
stringstream ssin(s);
string str;
vector v;
while(ssin >> str) v.push_back(str);
for (int i = 0 ; i < 26 ; i ++ ) ans[i].clear();
for (int i = 1 ; i < v.size() ; i ++ )
{
if(v[i][0] != '-' || v[i][1] < 'a' || v[i][1] > 'z' || v[i].size() > 2) break;
else if(mp[v[i][1]] == 2) ans[v[i][1]-'a'] = "*";
else if(mp[v[i][1]] == 1 && i + 1 < v.size() ) ans[v[i][1]-'a'] = v[i+1] , i ++ ;
else break;
}
for (int i = 0 ; i < 26 ; i ++ ) {
if(ans[i].size()) {
cout << "-" << char(i + 'a') << ' ';
if(mp[char(i + 'a')] == 1) cout << ans[i] << " ";
}
}
cout << endl;
}
return 0;
}
D. 无线网络
首先保证读懂题，然后将每个满足距离条件的路由器相连，将其构造成一个无向图。
默认其每个边权值为1，那么路由器1到其他路由器的距离就是中间经过的路由器数。
注意题目求的是最少中转路由器数，不是最少新增路由器数
那么也就转化成了求从路由器1到路由器2的最短路径，这里的最短路径=最少中转路由器
#include
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair pii;
const int N = 210,M = N * N;
ll n,m,k,r;
pii p[N];
int dist[N][N]; // dist[i][j]表示从路由器1到达路由器i，中间增设j个路由器的最短路径
int e[M],ne[M],h[N],idx;
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}
bool check(pii a,pii b)
{
ll d1 = a.x - b.x;
ll d2 = a.y - b.y;
return d1 * d1 + d2 * d2 <= r * r;
}
int bfs()
{
memset(dist,0x3f,sizeof dist);
queue q;
q.push({1,0});
dist[1][0] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
for (int i = h[t.x] ; ~i ; i = ne[i])
{
int j = e[i] , c = t.y;
if(j > n) c ++ ;
if(c <= k) {
if(dist[j][c] > dist[t.x][t.y] + 1) {
dist[j][c] = dist[t.x][t.y] + 1;
q.push({j,c});
}
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 0 ; i <= k ; i ++ )
ans = min(ans,dist[2][i]);
return ans-1;
}
int main()
{
memset(h,-1,sizeof h);
cin >> n >> m >> k >> r;
for (int i = 1 ; i <= n+m ; i ++ ) cin >> p[i].x >> p[i].y;
for (int i = 1 ; i <= n+m ; i ++ )
for (int j = i+1 ; j <= n+m ; j ++ )
if(check(p[i],p[j]))
add(i,j),add(j,i);
cout << bfs() << endl;
return 0;
}
E. 任务调度
这里用 cpu1，cpu2 代表两个 CPU ，用 gpu 表示 GPU
该题有几个需要注意的点
-
若一个进程使用 cpu1 + cpu2 或者 cpu1 + cpu2 + gpu ，那么其他进程没法执行，
所以这俩调度方法是等效的，且其放置顺序可以随机，只需要取其中的最小值即可。 -
假设只使用1，3调度方法，设 cpu1 的使用时间为 a，cpu2的使用时间为 b，gpu的使用时间为 c，
那么可以证明最少时间为 \(max(a，b，c)\)【可以自己画图证明一下】
所以设\(f(u,i,j,k)\)为实现前 u-1 个任务，且使用时间为 cpu1，cpu2，gpu 的使用时间为 \(i,j,k\) 时，
2或4调度方法的最少时间。
最终答案 = 1，3调度方法时间 + 2，4调度方法时间 = \(max(a, b, c) + f(u,i,j,k)\)
#include
using namespace std;
const int N = 210;
int q[N][3];
int f[2][N][N][N]; // f[u][i][j][k]代表前u-1个任务总共用i,j,k个cpu1，cpu2，gpu时使用的第三四种调度方式的最少时间
int main()
{
int n;
cin >> n;
int m=0;
int a,b,c,d;
for (int i = 1 ; i <= n ; i ++ )
{
cin >> a >> b >> c >> d;
q[i][0] = a , q[i][1] = c , q[i][2] = min(b,d);
m += a;
}
m = (m + 1) / 2;
memset(f,0x3f,sizeof f);
f[0][0][0][0] = 0;
// 枚举前u个任务
for (int u = 1 ; u <= n ; u ++ )
{
// 枚举i,j,k的值
for (int i = 0 ; i <= m ; i ++ )
{
for (int j = 0 ; j <= m ; j ++ )
{
for (int k = 0 ; k <= m ; k ++ )
{
int &v = f[u & 1][i][j][k];
register int x = q[u][0],y = q[u][1],z = q[u][2],t = u - 1 & 1; // t表示u-1时的f
v = f[t][i][j][k] + z;
if (i >= x) v = min(v, f[t][i - x][j][k]);
if (j >= x) v = min(v, f[t][i][j - x][k]);
if (i >= y && k >= y) v = min(v, f[t][i - y][j][k - y]);
if (j >= y && k >= y) v = min(v, f[t][i][j - y][k - y]);
}
}
}
}
int res = 0x3f3f3f3f;
for (int i = 0; i <= m; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= m; k ++ )
res = min(res, f[n & 1][i][j][k] + max(i, max(j, k)));
cout << res << endl;
return 0;
}