机票
战绩贴贴
发挥还算正常？？反正大家都没开出c，不过又被暴了555
A.Cashier
题意：
一天长度为L小时，有n个客人，每个客人从t时来，待l小时，只有没客人时才能休息，且休息一次时间长为a小时，求最多能休息多久（保证一个客人走了之后下一个客人才会来）。
思路：
由于题目给定的条件是一个客人走了之后下一个客人才来，所以我们可以直接将每两个客人走与来之间的间隔时间求出，再用此时间除以a，则可以求出每两个客人走与来之间可以休息的次数。
#define int long long const int maxn=1e5+1000; struct node{ int t,l; }mo[maxn]; signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,l,a,i; cin>>n>>l>>a; for(i=0;i<n;i++) { cin>>mo[i].t>>mo[i].l; } int ans=0,m1=0; for(i=0;i<n;i++) { ans+=((mo[i].t-m1)/a); m1=mo[i].t+mo[i].l; } ans+=((l-m1)/a); cout<<ans<<endl; return 0; }
B. Forgery
题意：
思路：
因为我做的实在是又臭又长（因为没想到正解瞎敲了快一百行）
裹jio布代码
思路：其实是个简单bfs输入地图后，枚举地图的格子，若能染色就染色，不能就枚举下一个。
如果目标状态不是’#’，不染色。
如果染色范围出了边界，不染色。
如果都没有，就将周围8个格子染成#。
染色完毕后，与目标状态比对。
若一样，输出YES，不一样，输出NO。
#include<bits/stdc++.h> using namespace std; int dx[8]={1,1,-1,-1,0,0,1,-1};//移动数组就不说啦。 int dy[8]={1,-1,1,-1,1,-1,0,0}; int n,m; char mubiao[1005][1005];//存目标地图。 char bian[1005][1005];//存我们用来搜索的地图，也是方便搜完后比对。 bool bidui() { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mubiao[i][j]!=bian[i][j])//一个一个挨着比对。 return false;//如果有不一样的，说明不行，返回false。 } } return true;//如果没有不一样的，说明可以，返回true。 } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>mubiao[i][j];//输入目标地图。 bian[i][j]='.';//要改变的地图，初始都是'.'。 } for(int x=1;x<=n;x++) for(int y=1;y<=m;y++) { int biao=1;//作为标记。 for(int z=0;z<8;z++) { int mx=x+dx[z]; int my=y+dy[z]; if(mx>n||mx<=0||my>m||my<=0)//如果出了边界，打标记，不能染色。 { biao=0; break; } else if(mubiao[mx][my]!='#')//如果目标状态不是'#'，打标记，不能染色。 { biao=0; break; } } if(biao==0)//如果上面被标记，选下一个点。 continue; for(int z=0;z<8;z++)//没有就染色。 { int mx=x+dx[z]; int my=y+dy[z]; bian[mx][my]='#';//全部都染上。 } } if(bidui())//比对。 cout<<"YES";//可以输出YES。 else cout<<"NO";//不能输出NO。 return 0; }
C. Sequence Transformation
题意：
读入一个正整数n。 你有一个长度为n的排列。 对于一次操作，我们需要做一下几步:
1.将目前序列内所有数的gcd加入答案中
2.将序列内随意删除一个数
3.如果序列为空，则停止操作，否则重复以上步骤 操作完毕后，我们将会得到一个答案序列。
要求输出字典序最大的那一个答案序列
思路:大多数都是打表找规律，
思路：
首先有个简单的结论是:对于任意全排列，gcd肯定都为1，并且每次操作的前n/2次都为1
因为相邻的两个数互质
根据字典序的定义，我们需要最大化每次入队的gcd
就是要贪心的判断每次对整体最好的选择是什么
所以我们第一步肯定是把所有的奇数删除，使得之后的gcd不会为1
删除偶数的时候其实可以发现剩下的数比如n=8时，删完之后剩下的有
2 4 6 8
可以看成
2x1 2x2 2x3 2x4
于是乎可以把问题转换为n/2之后的子问题，继续删奇数~
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; int a[maxn]; int main() { int n,i,j,t; cin>>n; int d1=1,m1=n; for(i=0;i<(n%2==1?n/2+1:n/2);i++) cout<<1<<" "; n-=n%2==1?n/2+1:n/2; while(n>3) { d1*=2; for(i=0;i<(n%2==1?n/2+1:n/2);i++) cout<<d1<<" "; n=n/2; } d1*=2; if(n==1) { cout<<m1<<endl; } else if(n==2) { cout<<d1<<" "<<d1*2<<endl; } else if(n==3) { cout<<d1<<" "<<d1<<" "<<d1*3<<endl; } return 0; }
