Counterfeit Dollar
模拟题，和昨天刚做的题是一样的，所以就不多解释了，具体可以看上一篇
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
string a,b,s;
int T,m;
int f[100];
bool ff[100];
int main()
{
scanf("%d",&T);
while(T--)
{
memset(f,0,sizeof(f));
for(int i = 0;i < 3; ++i)
{
cin>>a;
cin>>b;
cin>>s;
m = a.size();
if(s[0] == 'e')
for(int j = 0;j < m; ++j)
{
f[a[j] - 'A' + 1] = 1;
f[b[j] - 'A' + 1] = 1;
}
else
{
memset(ff,0,sizeof(ff));
for(int j = 0;j < m; ++j)
{
if(s[0] == 'u')
{
if(f[a[j] - 'A' + 1] == -2) f[a[j] - 'A' + 1] = 1;
else if(f[a[j] - 'A' + 1] != 1) f[a[j] - 'A' + 1] = -1;
if(f[b[j] - 'A' + 1] == -1) f[b[j] - 'A' + 1] = 1;
else if(f[b[j] - 'A' + 1] != 1) f[b[j] - 'A' + 1] = -2;
}
else
{
if(f[a[j] - 'A' + 1] == -1) f[a[j] - 'A' + 1] = 1;
else if(f[a[j] - 'A' + 1] != 1) f[a[j] - 'A' + 1] = -2;
if(f[b[j] - 'A' + 1] == -2) f[b[j] - 'A' + 1] = 1;
else if(f[b[j] - 'A' + 1] != 1) f[b[j] - 'A' + 1] = -1;
}
ff[a[j] - 'A' + 1] = 1;
ff[b[j] - 'A' + 1] = 1;
}
for(int j = 1;j <= 12; ++j)
{
if(!ff[j]) f[j] = 1;
if(!ff[j]) f[j] = 1;
}
}
}
for(int i = 1;i <= 12; ++i)
{
if(f[i] != 1)
{
printf("%c is the counterfeit coin and it is ",i + 'A' - 1);
if(f[i] == -2) printf("light.\n");
else printf("heavy.\n");
break;
}
}
}
return 0;
}
搜索 1033（读题是个技术活啊，感谢百度翻译给予我真挚的爱）
You are taking part in the development of a "New Generation" operating system and the NG file system. In this file system all disk space is divided into N clusters of the equal sizes, numbered by integers from 1 to N. Each file occupies one or more clusters in arbitrary areas of the disk. All clusters that are not occupied by files are considered to be free. A file can be read from the disk in the fastest way, if all its clusters are situated in the successive disk clusters in the natural order.
Rotation of the disk with constant speed implies that various amounts of time are needed for accessing its clusters. Therefore, reading of clusters located near the beginning of the disk performs faster than reading of the ones located near its ending. Thus, all files are numbered beforehand by integers from 1 to K in the order of descending frequency of access. Under the optimal placing of the files on the disk the file number 1 will occupy clusters 1, 2, ..., S1, the file number 2 will occupy clusters S1+1, S1+2, ..., S1+S2 and so on (here Si is the number of clusters which the i-th file occupies).
In order to place the files on the disk in the optimal way cluster-moving operations are executed. One cluster-moving operation includes reading of one occupied cluster from the disk to the memory and writing its contents to some free cluster. After that the first of them is declared free, and the second one is declared occupied.
Your goal is to place the files on the disk in the optimal way by executing the minimal possible number of cluster-moving operations.
Input
The first line of the input file contains two integers N and K separated by a space(1 <= K < N <= 10000).Then K lines follow, each of them describes one file. The description of the i-th file starts with the integer Si that represents the number of clusters in the i-th file (1 <= Si < N). Then Si integers follow separated by spaces, which indicate the cluster numbers of this file on the disk in the natural order.
All cluster numbers in the input file are different and there is always at least one free cluster on the disk.
Output
Your program should write to the output file any sequence of cluster-moving operations that are needed in order to place the files on the disk in the optimal way. Two integers Pj and Qj separated by a single space should represent each cluster-moving operation. Pj gives the cluster number that the data should be moved FROM and Qj gives the cluster number that this data should be moved TO.
The number of cluster-moving operations executed should be as small as possible. If the files on the disk are already placed in the optimal way the output should contain only the string "No optimization needed".
Sample Input
20 3
4 2 3 11 12
1 7
3 18 5 10 Sample Output
2 1
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7 说真的读题读了特别久，最后翻译了一下都没明白，果然是太菜了，嘤嘤嘤，后来终于勉强读懂了，发现不会做，真是苍天啊
解释：
首先是保存数据的问题，开二维数组挂了，所以改为vector就行了，至少不是MLE了不是
后来想啊，无非就是一个问题，按顺序把数字放到指定的位置，就有两种情况，
1）最终位置里没有文件，那么就可以直接移动了
2） 难点就在这里了，如果有文件的话，就应该把里面的文件移走，然后再把它移过来，关键在于，把原来的文件移到哪里才合适呢，随便找一个吗？显然不可以。怎么移？ 我的思绪就此乱掉555~~~
原来遗忘了这个点本来就在目标位置的情况 && No optimization needed 这句话，加上加上
#include<iostream> //这是一份WA的代码，见证我艰难做出此题的过程哈哈哈
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int n,k,tot;
bool f[10010],flag;
int t[10010],s[10010],xx[10010],yy[10010];
vector<int>a[10010];
void dfs(int file,int num)
{
if(file == k) return;
if(a[file][num] == t[a[file][num]])
if(num + 1 < s[file]) dfs(file ,num + 1);
else dfs(file + 1,0);
flag = 1;
if(!f[t[a[file][num]]]) //如果最终位置空的话直接移动即可
{
f[t[a[file][num]]] = 1;
f[a[file][num]] = 0;
printf("%d %d\n",a[file][num],t[a[file][num]]);
if(num + 1 < s[file]) dfs(file ,num + 1);
else dfs(file + 1,0);
}
else //如果最终位置不空的话，，咋办呢
{
for(int i = n; i >= 1; --i)
{
if(!f[i])
{
printf("%d %d\n",a[file][num],i);
t[i] = t[a[file][num]];
f[a[file][num]] = 0;
f[i] = 1;
if(num + 1 < s[file]) dfs(file ,num + 1);
else dfs(file + 1,0);
break;
}
}
}
}
int main()
{
scanf("%d%d",&n,&k);
tot = 0;
for(int i = 0;i < k; ++i)
{
scanf("%d",&s[i]);
for(int j = 0;j < s[i]; ++j)
{
int x;
scanf("%d",&x);
a[i].push_back(x);
f[x] = 1;
t[x] = ++tot; //记录最终的位置
xx[x] = i;
yy[x] = j;
}
}
flag = 0;
dfs(0,0);
if(!flag) printf("No optimization needed\n");
else
for(int i = tot + 1;i <= n; ++i)
if(f[i]) printf("%d %d\n",i,t[i]);
return 0;
}
附上一篇看起来挺好的题解
https://www.cnblogs.com/damacheng/archive/2010/09/24/1833983.html
题解说的很清楚，我就直接上代码啦
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
#include<stack>
using namespace std;
int a[10001]; //簇的使用情况
int n, m; //簇的总数和文件个数
int tot = 1; //文件片段起始编号
int num = 0; //操作总数
stack<int> s;
void work()
{
int next;
for(int i = 1; i <= n; ++i)
{
if(a[i] == i) continue;
if(a[i] != 0)
{
s.push(i);
next = a[i];
bool is_circle = 0;
while(true)
{
if(a[next] == i)
{
is_circle = 1;
break;
}
else
if(!a[next])
{
is_circle = 0;
break;
}
s.push(next);
next = a[next];
}
int t, j;
if(is_circle)
{
for(j = n; j >= 0; --j)
if(a[j] == 0) break;
printf("%d %d\n", next, j);
a[j] = a[next];
while(!s.empty())
{
t = s.top();
printf("%d %d\n", t, next);
a[next] = a[t];
next = t;
s.pop();
num++;
}
a[next] = a[j];
a[j] = 0;
printf("%d %d\n", j, next);
}
else
{
while(!s.empty())
{
t = s.top();
printf("%d %d\n", t, next);
a[next] = a[t];
next = t;
s.pop();
num++;
}
a[next] = 0;
}
}
}
if(!num) printf("No optimization needed\n");
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; ++i)
{
int n, t;
scanf("%d", &n);
for(int j = 0; j < n; ++j)
{
scanf("%d", &t);
a[t] = tot++;
}
}
work();
return 0;
}
京公网安备 11010502036488号