Winter Camp I (下）
M题： Stones
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N;
struct stone
{
int p,d;
};
stone pl;
struct cmp
{
bool operator()(const stone a,const stone b)
{
if(a.p!=b.p)
return a.p>b.p;
else
return a.d>b.d;
}
};
int main()
{
int T;
priority_queue<stone,vector<stone>,cmp>q;
cin>>T;
while(T--)
{
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%d%d",&pl.p,&pl.d);
q.push(pl);
}
int flag=1;
while(!q.empty())
{
pl=q.top();
q.pop();
if(flag)
{
pl.p+=pl.d;//把奇数次遇到的石头的位置距离和投掷距离相加，然后再入队
q.push(pl);
}
flag=!flag;
}
printf("%d\n",pl.p);
}
return 0;
}
从M题以后的都是STL相关的问题，M题是STL中对优先队列的考察
题意：在一条直线道路上有n个石头，向前走遇到一个数一个，如果遇到的是位置是第奇数个那就把这个石头往前扔距离stone.d， 如果是第偶数个，就跳过不管。若遇到位置相同的，优先看见那个投掷距离短的石子。问遇到的最后一个石头距离出发点的位置是多少。
思路：本题是对其题意在算法上进行一个模拟，构造一个结构体用来记录石子的初始位置和投掷的距离。用优先队列来存储这些信息，并且根据题意，要让那些位置距离小的，投掷距离近的石头权重高，所以还要涉及到自己重新构建优先的判定规则。当遇到奇数时，把投掷后的距离累加到位置信息上，作为一个新的石子入队，然后把当前石子的信息出队删除，反复进行，直到队空结束。
知识点：优先队列的使用及优先级的设定
Q题： Word Amalgamation
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int main()
{
map<string,string>word;
string str,tmp;
while(cin>>str&&str!="XXXXXX")
{
tmp=str;
sort(str.begin(),str.end());
word.insert(pair<string,string>(tmp,str));
}
while(cin>>str)
{
int flag=1;
if(str=="XXXXXX")
break;
sort(str.begin(),str.end());
map<string,string>::iterator it;
for(it=word.begin();it!=word.end();it++)
{
if(str==it->second)
{
cout<<it->first<<endl;
flag=0;
}
}
if(flag)
cout<<"NOT A VALID WORD"<<endl;
printf("******\n");
}
return 0;
}
题意：就是先输入一个字典然后在输入一些乱码的单词，找出字典中"对应"的单词并输出，如果有多个那就按字典排序输出，如果没有就输出一行NOT A VALID WORD 当一个单词搜索完后不论找没找到都要输出一行******表示该单词的搜索结束。
思路：本题在对字典输入后，就要用sort对字典中的每个单词进行排序，（默认排序从小到大即可），然后用map<string,string>来分别记录键值和对应的表示，这里的键值就是字典中原本的单词，对应的表示就是单词排序后的样子。添加到map里的方法是用Value.insert()函数。
之后再输入乱序的单词，这里的关键点就是如何比较的问题，其实思路也不难，就是把这个乱序的单词也用sort（）函数排序，当map里的表示与输入后的排序相同，那么就输出map里的键值，否则就是 Not a vaild word.
知识点：这里用到的map函数，map<string,string>word：map的构造，键值和表示都是字符串型。word.insert()往map里插入数值。遍历所有map记录的数据要用到迭代器：
map<string,string>::iterator it，这里it是一个类似于指针的东西，调用其第一个或者第二个内容的方式为（*it）.first或it->first,
用迭代器遍历整个map的语句是
for(it=word.begin();it!=word.end();i++).
O题： What Are You Talking About
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string,string>dic;
string s1,s2;
char s[500],aa[500],ss[100];
int k=0;
scanf("%s",ss);
while(cin>>s1)
{
if(s1=="END")
break;
getchar();
getline(cin,s2);
dic[s2]=s1;
}
getchar();
while(gets(s))
{
if(strcmp(s,"END")==0)
break;
if(strcmp(s,"START")==0)
continue;
for(int i=0;s[i]!='\0';i++)
{
if(islower(s[i]))
aa[k++]=s[i];
else
{
aa[k]='\0';
if(dic.count(aa))
cout<<dic[aa];
else
printf("%s",aa);
printf("%c",s[i]);
k=0;
}
}
printf("\n");
}
return 0;
}
题意：就是让你把乱码符号翻译成正常的英文并输出。
思路：首先是用map构建字典，之后通过gets()函数来读取一段含空格和标点的句子，并通过islower()来判断是否是英文字符以及map类下的count函数来判断是否是满足在字典里的乱码，满足的话则按字典规则里的对应关系输出这个英文单词，否则直接把这个乱码或非英文字符输出即可.
知识点：第一次提交的时候，系统显示TLE，说明程序不够简洁超时了，之后又提交了4次，前3次仍然是TLE,最后一次是数组开小了，总共5次提交，第六次的时候终于A了。
简单说一下程序优化的地方，虽然优化后时间花费的时间仍然很长
第一处是把用cin与cout输入输出的，能改的都用scanf与printf函数代替了，毕竟C语言接近底层还是相对C++的输入输出来说要快的。
第二处我用的是STL的map类下的insert函数来添加数据，但这显然耗时，之后用map是关联数组的特性，改成数组赋值的方式，判断是否与字典里的乱码字符想匹配，之前用的是map的迭代器来对整个map进行遍历，之后改成使用map下的count函数来进行检测，总体上是更改了这么多，现在简单说一下这个题里的知识点。
这个题仍然是对STL中map的应用，偏向map的库函数的方法，
islower(a)函数：检查参数a是否为小写英文字母, 若参数a为小写英文字母，则返回TRUE，否则返回NULL(0),头文件是ctype.h
map.count(r),r是否能在键值中找到，可以则返回TRUE，不可以则返回FALSE。
gets（）函数从标准输入设备读入字符串函数，可以无限读取，不会判断上限，以回车结束读取，所以要确保buffer的空间足够大，以便在执行操作时不会溢出
getline()函数是专门给string类型变量输入字符串的，不写结束符时，默认以回车结束，同时输入结束时回车会从输入流中取出并丢弃。
F题： Crashing Robots
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int A,B;//A:length(EW),B:(NS).
int N,M;//N:the number of robots,M:the number of instructions
int maze[120][120];
int dirx[4]={-1,0,1,0};
int diry[4]={0,1,0,-1};
int xi,yi;//记录机器人的初始位置
char di;//初始转向
int num,re;//执行指令的机器人型号和重复次数
char act;
struct Robot
{
int x;
int y;
int d;
}robot[105];
bool forward(int num,int re)
{
int xf,yf,df;
xf=robot[num].x;
yf=robot[num].y;
df=robot[num].d;
maze[xf][yf]=0;
for(int i=0;i<re;i++)
{
xf+=dirx[df];
yf+=diry[df];
if(xf<1||xf>A||yf<1||yf>B)
{
cout<<"Robot "<<num<<" crashes into the wall"<<endl;
return false;
}
if(maze[xf][yf])
{
cout<<"Robot "<<num<<" crashes into robot "<<maze[xf][yf]<<endl;
return false;
}
}
robot[num].x=xf;
robot[num].y=yf;
maze[xf][yf]=num;
return true;
}
bool action(int num,char act,int re)
{
switch(act)
{
case'F':return forward(num,re);
case'L':robot[num].d=(robot[num].d-re%4+4)%4;break;
case'R':robot[num].d=(robot[num].d+re%4)%4;break;
}
return true;
}
int main()
{
int K;
bool flag;
cin>>K;
while(K--)
{
scanf("%d%d",&A,&B);
scanf("%d%d",&N,&M);
memset(maze,0,sizeof(maze));
memset(robot,0,sizeof(robot));
for(int i=1;i<=N;i++)
{
cin>>xi>>yi>>di;
robot[i].x=xi;
robot[i].y=yi;
maze[xi][yi]=i;
switch(di)
{
case 'W':robot[i].d=0;break;
case 'N':robot[i].d=1;break;
case 'E':robot[i].d=2;break;
case 'S':robot[i].d=3;break;
default:robot[i].d=-1;
}
}
flag=true;
for(int i=0;i<M;i++)
{
cin>>num>>act>>re;
if(flag)
flag=action(num,act,re);
}
if(flag)
printf("OK\n");
}
return 0;
}
这题其实不难，但WA了许多次，原因在于数组下标写错，代码大小写问题，下次遇到搞不出来的时候去POJ找些数据测试超级好用，一下子该对AC了。
哦，对了，cin在空格结束后系统会从缓存中取出空格弃掉，不错，适合整型和字符一起输入的时候。
R题： Matrix multiplication
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int a[806][806],b[806][806],c[806][806];
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
a[i][j]%=3;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&b[i][j]);
b[i][j]%=3;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(!a[i][j])
continue;
for(int k=0;k<n;k++)
c[i][k]+=a[i][j]*b[j][k];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(j==n-1)
printf("%d\n",c[i][j]%3);
else
printf("%d ",c[i][j]%3);
}
}
}
return 0;
}
本题是一道常规的矩阵乘法题，常见的思路使用两个二维数组存储每个矩阵里的值，然后再模拟矩阵运算的乘法。
下面的代码是用于模拟矩阵运算乘法的代码：
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(!a[i][j])
continue;
for(int k=0;k<n;k++)
c[i][k]+=a[i][j]*b[j][k];
}
}
因为这里要求结果还必须对3取模，所以我们的思路是在输入时对3取个模，在输出时对3取个模。输入时对3取个模的作用是在后面的矩阵乘法过程中把0项直接跳过，方便简化后面的运算。输出结果取模，是为防止之前取完模后，相加又多了3的倍数，所以要再次取模，防止出现与运算结果不符的情况。
N题： Demonstration
题目so long，来个题目链接：
http://codeforces.com/problemset/problem/191/B
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
ll a[100005],b[100005];
ll n,k,m,i,sum;
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>n>>k>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+n,cmp);
sum=0;
for(int i=1;i<k;i++)
{
sum+=b[i];
}
for(int i=1;i<n;i++)
{
if(a[i]>=b[k])//地之前选择了
{
if(sum+b[k]>m)
{
cout<<i<<endl;
return 0;
}
}
else if(sum+a[i]>m)//广场之前没选
{
cout<<i<<endl;
return 0;
}
}
cout<<n<<endl;
return 0;
}
这题是一个贪心算法的题目，但题意真的是好难读懂啊
题意：政府有N块地，现在有人想要反对政府，要举行示威，向政府申请场地。
这N块第，按照里政府中心的距离远近编号为1-N, 1号地点最近。
政府总是把反对者安排到最后一块地点，但要找个理由
于是当反对者申请一块地的时候，政府就安排一个长期活动占用那个地方。当然这是要钱的
最后一块地最差，也是政府所希望的，所以政府不花钱。
现在问反对者能得到到最好的地是那一块。
有几个限制条件，也是输入数据。
地的块数，政府的钱，工作天数（也是反对者最多申请的次数）
后面输入是从市中心到郊区的公园政府在那里办活动的钱数
思路：我们把前N-1块地排个序，然后去前k-1个数字，累加，这样能最大程度耗光政府的钱，那么我们最后一天就能申请到好的地
然后我们从头开始找最好的地
分为两种情况：
一个是这块地在我们之前已经选过，这个时候判断一下sum+b【k】和m的关系就可以，即是判定花钱最多的地方能否突破政府的预算，若能突破，那么则可以在最后一天申请最好的地方，只要调整一下申请的顺序即可
一个是这块地之前没选过，但sum+a[i]>m，只要大于政府预算即可实现最好地段公园的申请。
知识点：sort()函数的三个参数
（1）第一个是要排序的数组的起始地址。
（2）第二个是结束的地址（最后一位要排序的地址的下一地址）
（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。