机试资料: https://pan.baidu.com/s/1QKfvbN-sV-3l89kUI-dxgQ 密码:1f65
从来没打过ACM，人都是逼出来的…
2017 interview
生活在在外星球X上的小Z想要找一些小朋友组成一个舞蹈团，于是他在网上发布了信息，一共有 $n$ 个人报名面试。面试必须按照报名的顺序依次进行。小Z可以选择在面试完若干小朋友以后，在所有已经面试过的小朋友中进行任意顺序的挑选，以组合成一个舞蹈团。虽然说是小朋友，但是外星球X上的生态环境和地球上的不太一样，这些小朋友的身高可能相差很大。小Z希望组建的这个舞蹈团要求至少有 $m$ 个小朋友，并且这些小朋友的最高身高和最低身高之差不能超过 $k$ 个长度单位。现在知道了这些小朋友的身高信息，问小Z至少要面试多少小朋友才能在已经面试过的小朋友中选出不少于 $m$ 个组成舞蹈团。
过了14个测试点！！！
# include<algorithm>
# include<vector>
# include<iostream>
using namespace std;
typedef struct{int id;int h;} student;
bool operator <(const student& a,const student & b){return (a.h)<(b.h);}
int n,m,k,tall=0;
vector<student> stu;
vector<int> highid;
void init(){
student temp;
cin >> n >> m >> k;
for(int i=0;i<n;i++){
temp.id = i;
cin >> temp.h;
stu.push_back(temp);
}
}
void pick(){
for(int i = 0;i<=n-m;i++){ //排序
sort(stu.begin(),stu.begin()+m+i);
for(int j = 0;j<=i;j++){//检查个头
if(stu[j+m-1].h-stu[j].h<=k){
for(int y=j;y<j+m;y++){//找最大id
if(stu[y].id>tall) tall = stu[y].id;
}
cout<<tall+1<<endl;
return;
}
}
}
cout<<"impossible"<<endl;
}
int main(){
init();
pick();
return 0;
}
2017多项式求和
小K最近刚刚习得了一种非常酷炫的多项式求和技巧，可以对某几类特殊的多项式进行运算。非常不幸的是，小K发现老师在布置作业时抄错了数据，导致一道题并不能用刚学的方法来解，于是希望你能帮忙写一个程序跑一跑。给出一个 $m$ 阶多项式\(f(x)=\sum_{i=0}^mb_ix^i\)对给定的正整数 $a$ ，求\(S(n)=\sum_{k=0}^na^kf(k)\)由于这个数可能比较大，所以你只需计算 $S(n)$ 对 $10^9+7$ 取模后的值（即计算除以 $10^9+7$ 后的余数）。
只能过两个测试点！！！
# include <stdio.h>
# include <iostream>
# define MAX 1000000007
# define ll long long
using namespace std;
ll n,m,a,*b;
long long mul(long long a,long long b,long long mod) {
long long res = 0;
while(b > 0){
if( (b&1) != 0) // 二进制最低位是1 --> 加上 a的 2^i 倍, 快速幂是乘上a的2^i ）
res = ( res + a) % mod;
a = (a << 1) % mod; // a = a * 2 a随着b中二进制位数而扩大 每次 扩大两倍。
b >>= 1; // b -> b/2 右移 去掉最后一位 因为当前最后一位我们用完了，
}
return res;
}
long long pow(long long a,long long n,long long mod) {
long long res = 1;
while(n > 0) {
if(n & 1)
res = mul(res,a,mod);
a = mul(a,a,mod);
n >>= 1;
}
return res;
}
void init(){
cin>>n>>m>>a;
b = new ll[m+1];
for(ll i=0;i<=m;i++){
cin>>b[i];
}
}
ll f(ll x){
ll result=0;
for(ll i=0;i<=m;i++){
result+=mul(b[i],pow(x,i,MAX),MAX);
result%=MAX;
}
return result;
}
ll s(){
ll result=0;
for(ll i = 0;i<=n;i++){
result+=mul(pow(a,i,MAX),f(i),MAX);
result%=MAX;
}
return result;
}
int main(){
init();
cout<<s()<<endl;
return 0;
}
2018葱的战争
一个n乘m的棋盘，上面有k根葱，每根葱面朝方向为d（0123分别表示上下左右），没跟葱一个战斗力f。每隔时间葱会向面朝方向走一格，如果遇到棋盘边界，那么他将把面朝方向转180度（此回合葱不会走动），如果某个时刻有两个或以上的葱在同一位置，那么他们将发生战争，只有战斗力最高的葱存活，其他的葱全部原地枯萎，不在走动，求经过t时间后所有葱的位置
输入：第一行n m k，然后接下来k行每根葱的信息x y d f（坐标，方向，战斗力），最后一行输入时间t 输出：k行，分别表示每个葱的位置。 数据范围：n和m在100内，k在1000内，t在1000内，f在1000内，保证初始每颗葱位置不同，战斗力不同。
以下代码测试点通过
# include<iostream>
# include<map>
# include<vector>
using namespace std;
typedef struct{int x,y;} position;
typedef struct{int id,f;} idfight;
typedef struct{int id;position p;int d;int f;bool live;} cong;
typedef vector<cong> conglist;
conglist all_cong;
map<int,vector<idfight> >war_map;
int n,m,k,times;
void init(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
int x,y,d,f;
cin >> x >>y>>d>>f;
cong c1 ={i,{x,y},d,f,1};
all_cong.push_back(c1);
}
cin >> times;
}
void action(cong &c){
if(c.live){
switch(c.d){
case 0: if(c.p.y==m) c.d=1;else c.p.y++;break;
case 1: if(c.p.y==1) c.d=0;else c.p.y--;break;
case 2: if(c.p.x==1) c.d=3;else c.p.x--;break;
case 3: if(c.p.y==n) c.d=2;else c.p.x++;break;
default:;break;
}
int pi = c.p.x*1000+c.p.y;
idfight idf = {c.id,c.f};
war_map[pi].push_back(idf);
}
}
void printans(){
for(vector<cong>::iterator i = all_cong.begin();i!=all_cong.end();i++)
cout<<(*i).p.y<<" "<<(*i).p.x<<endl;
}
void fight(){
map<int,vector<idfight> >::iterator it;
it = war_map.begin();
while(it!=war_map.end()){
if((*it).second.size()>1){
int max = 0;
for(vector<idfight>::iterator i = (*it).second.begin();i!=(*it).second.end();i++){
if((*i).f>max)max = (*i).f;
}
for(vector<idfight>::iterator i = (*it).second.begin();i!=(*it).second.end();i++){
if((*i).f<max) all_cong[(*i).id].live=0;
}
}
it++;
}
}
int main() {
init();
while(times--){
for(vector<cong>::iterator i = all_cong.begin();i!=all_cong.end();i++){
action(*i);
}
fight();
war_map.clear();
}
printans();
return 0;
}
2018路径
有n个点，每个点有一个权值，每两点间的不同边的个数为他们权值相与得到的值的二进制数字中的1的个数（边为有向边，有第i指向第j，i小于j）求第1个点到第n个点的路径个数（当且仅当不止一条边不同才被称为两条不同的路径），由于数据很大，对991247取模。
输入：第1行n，第二行分别试每个点权值 输出：路径个数 数据范围:n在2e5内，权值大小在1e9内
# include<iostream>
# include<bitset>
# include<vector>
# define MAX_BIT 32
using namespace std;
vector<int> power;
int n;
void init(){
cin>>n;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
power.push_back(temp);
}
}
int countones(int a,int b){
int c = a&b;
bitset<MAX_BIT> bt(c);
return bt.count();
}
int calc(int n){
return n==1?
countones(power[0],power[1]):
countones(power[0],power[n])+
calc(n-1)*countones(power[n],power[n-1])%991127;
}
int main(){
init();
cout<<calc(n-1)%991127<<endl;
return 0;
}
2018四种操作
有一个n个元素的数列,元素的值只能是0 1 2三个数中的一个，定义四种操作，(1 i x)表示为把第i位替换成x，x也只能是0 1 2三个数中的一个，(2 i j)表示把第i个数到第j个数所有的元素值加1，并对3取模，(3 i j)表示把第i个数到第j个数之间的序列的颠倒顺序，(4 i j)表示查询第i个数到第j个数之间的序列是否存在三个或以上相同数，如果有，输出yes，否则输出no
输入：第一行输入n，接下来一行输入n个数，保证是0 1 2中的一个，第三行输入一个数q，表示操作个数，接下来q行输入q种操作 输出：每次第四次操作时，输出yes或者no 数据范围：不记得了
# include<iostream>
# include<vector>
# include<algorithm>
using namespace std;
typedef struct {int x,y,z;} comm;
vector<int> numlist;
vector<comm> commlist;
int n,q;
void init(){
int temp;
cin>>n;
while(n--){
cin>>temp;
numlist.push_back(temp);
}
cin>>q;
int x,y,z;
while(q--){
cin>>x>>y>>z;
comm command = {x,y,z};
commlist.push_back(command);
}
}
void printdata(){
vector<int>::iterator it;
it = numlist.begin();
while(it!=numlist.end()){
cout<<(*it)<<" ";
it++;
}
cout<<endl;
}
void action_1(int i,int x){
numlist[i-1]=x;
}
void action_2(int i ,int j){
i--;j--;
for(;i<=j;i++){
numlist[i]=(numlist[i]+1)%3;
}
}
void action_3(int i ,int j){
i--;
reverse(numlist.begin()+i,numlist.begin()+j);
}
void action_4(int i , int j){
i--;
int a,b,c;
a = count(numlist.begin()+i,numlist.begin()+j,0);
b = count(numlist.begin()+i,numlist.begin()+j,1);
c = count(numlist.begin()+i,numlist.begin()+j,2);
if((a>2)||(b>2)||(c>2))cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
int main(){
init();
vector<comm>::iterator i;
i = commlist.begin();
while(i!=commlist.end()){
switch((*i).x){
case 1:action_1((*i).y,(*i).z);break;
case 2:action_2((*i).y,(*i).z);break;
case 3:action_3((*i).y,(*i).z);break;
case 4:action_4((*i).y,(*i).z);break;
default:;
}
i++;
}
printdata();
return 0;
}
2019判形状（推研）
输入第一行n和m，给n个节点m条边的有向图。判断是单链/树/有环/无环？输出最细致的定义。注意合法数据要求后面有m行，每一行是一个空格隔开的正整数。
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define MAX(a, b) ((a) > (b) ? (a) : (b) )
using namespace std;
int n,m;
vector<int> inDegreelist,outDegreelist;
//定义图的定点
typedef struct Vertex {
int id,inDegree,outDegree;
vector<int> connectors; //存储节点的后续连接顶点编号
Vertex() : id(-1),inDegree(0),outDegree(0) {}
Vertex(int nid) : id(nid),inDegree(0),outDegree(0) {}
} Vertex;
//定义Graph的邻接表表示
typedef struct Graph {
vector<Vertex> vertexs; //存储定点信息
int nVertexs; //计数：邻接数
bool isDAG; //标志：是有向图吗
Graph(int n, bool isDAG) : nVertexs(n), isDAG(isDAG) { vertexs.resize(n); }
Graph() : nVertexs(1), isDAG(1) { vertexs.resize(1); }
//向图中添加边
bool addEdge(int id1, int id2) {
if (!(MAX(id1, id2) < vertexs.size())) return false;
if (isDAG) {
vertexs[id1].connectors.push_back(id2);
vertexs[id1].outDegree++;
vertexs[id2].inDegree++;
}
else {
vertexs[id1].connectors.push_back(id2);
vertexs[id2].connectors.push_back(id1);
vertexs[id1].outDegree++;
vertexs[id1].inDegree++;
vertexs[id2].outDegree++;
vertexs[id2].inDegree++;
}
return true;
}
} Graph;
Graph g;
void init(){
cin>>n>>m;
g=Graph(n, true);
int src,dst;
while(m--){
cin>>src>>dst;
g.addEdge(src,dst);
}
vector<Vertex>::iterator it = g.vertexs.begin();
while(it!=g.vertexs.end()){
inDegreelist.push_back(it->inDegree);
outDegreelist.push_back(it->outDegree);
it++;
}
}
int countin(int n){
return count(inDegreelist.begin(),inDegreelist.end(),n);
}
int countout(int n){
return count(outDegreelist.begin(),outDegreelist.end(),n);
}
bool Is_List(){
//有一个inDegree为0的头和一个outDegree为0的尾，且其余节点入度与出度都为1;
return (countin(0)==1)&&(countout(0)==1)&&(countin(1)==n-1)&&(countout(1)==n-1);
}
bool Is_Tree(){
//有一个inDegree为0的头且其余节点inDegree均为1，且不是链表;
return (countin(0)==1)&&(countin(1)==n-1);
}
bool topologicalSort(){//拓扑排序判断有环无环
int num=0;//记录加入拓扑排序的顶点数
queue<int> q;
for(int i=0;i<n;i++){
if(inDegreelist[i]==0){
q.push(i);//将所有入度为0的顶点入队
}
}
while(!q.empty()){
int u=q.front();//取队首顶点u
q.pop();
for(int i=0;i<g.vertexs[u].connectors.size();i++){
int v=g.vertexs[u].connectors[i];//u的后继节点v
inDegreelist[v]--;//v的入度减1
if(inDegreelist[v]==0){//顶点v的入度减为0则入队
q.push(v);
}
}
g.vertexs[u].connectors.clear();//清空u的所有出边
num++;//加入拓扑排序的顶点数加1
}
if(num==n) return true;//加入拓扑排序的顶点为n，则拓扑排序成功，图无环
else return false;//否则拓扑排序失败，图有环
}
int main(){
init();
if(n==0||m==0){
cout<<"error"<<endl;
}
if(Is_List()){
cout<<"list"<<endl;
}
else if(Is_Tree()){
cout<<"tree"<<endl;
}
else if(topologicalSort()){
cout<<"no ring"<<endl;
}
else{
cout<<"have ring"<<endl;
}
return 0;
}
2019统计众数
某个序列有n个正整数，每个正整数都是m位数。某科研人员想统计该序列各个位的“众数”。第i位的众数是指，n个正整数的第i位出现次数最多的最小数字，最低位（个位）是第1位，最高是第m位。
输入：
第一行两个正整数n,m
第二行包含n个正整数，用一个空格隔开
输出：
共m行，每行一个整数，第i行表示第i位的众数
# include <iostream>
# include <vector>
# include <cmath>
# include <algorithm>
using namespace std;
vector<int> datain;
vector< vector<int> > datalist;
int n,m;
void init(){
cin>>n>>m;
for(int i=0;i<n;i++){
int temp;
cin>> temp;
datain.push_back(temp);
}
datalist.resize(m+1);
}
int countnum(vector<int> vc){
int max=-1;
int id=-1;
for(int i=0;i<10;i++){
int t = count(vc.begin(), vc.end(),i);
if(t>max){
max=t;
id=i;
}
}
return id;
}
void check(){
for(int i=0;i<n;i++){
for(int j=1;j<=m;j++){
int k = (datain[i]%(int)pow(10.0,j))/pow(10.0,j-1);
datalist[j].push_back(k);
}
}
}
int main(){
init();
check();
for(int i=1;i<=m;i++)cout<<countnum(datalist[i])<<endl;
return 0;
}