第十五届中北大学算法与程序设计竞赛（公开赛）代码笔记本-

https://www.yyycode.cn/index.php/2020/05/24/%e7%ac%ac%e5%8d%81%e4%ba%94%e5%b1%8a%e4%b8%ad%e5%8c%97%e5%a4%a7%e5%ad%a6%e7%ae%97%e6%b3%95%e4%b8%8e%e7%a8%8b%e5%ba%8f%e8%ae%be%e8%ae%a1%e7%ab%9e%e8%b5%9b%ef%bc%88%e5%85%ac%e5%bc%80%e8%b5%9b%ef%bc%89/

俄罗斯方块

链接：https://ac.nowcoder.com/acm/contest/5188/A
来源：牛客网

玩一个简化版的俄罗斯方块，只有10*10大小的二维平面，且只有四种图案，不会翻转，一行满后不消除，四种图案对应四个编号1，2，3，4，现在给出你所有图案按照先后顺序的下落坐标，你可以将最后的样子输出吗？ 注：一个点处如果有方块存在则表示成1，否则为0，也即最后输出一个10*10的01矩阵。 1：

2：

3：

4：

输入描述:

 第一行输入一个正整数n，表示接下来有n个图案落下，保证0<=n<=10。接下来n行，每行两个数字id，x。id表示图案的种类，保证1<=id<=4。x表示图案的左下角所在的横坐标。保证数据合法，不会出现超出10*10边界的情况。

输出描述:

 输出一个10*10大小的矩阵表示最后的形状，保证输出的图案一定可以放在10*10的矩阵中。

示例1

输入

复制 3 4 1 1 4 2 1

 3 4 1 1 4 2 1

输出

复制 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0

 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0

说明

 如图为样例一的情形

做法：就模拟，注意如果下面有东西要叠加…然后我wa了2回因为我把那个一条长度为4的看成长度为3的了

 #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5; typedef long long LL; LL ma[15][15]; int main(void) {      LL t;cin>>t;      for(LL f=1;f<=t;f++)         {             int id;int x;             cin>>id>>x;             if(id==1)             {                 int pos=10;                     for(int j=1;j<=10;j++)                         {                             if(ma[j][x]==1||ma[j][x+1]==1||ma[j-1][x]==1||ma[j-1][x+1]==1)                             {                                 pos=j;break;                                    }                         }                     ///j为行，横着的                     for(int j=pos;j>=1;j--)                     {                         ///x代表列                         ///左边和右边的为空                         if(ma[j][x]==0&&ma[j][x+1]==0&&ma[j-1][x]==0&&ma[j-1][x+1]==0)                          {                             ma[j][x]=1;                             ma[j][x+1]=1;                             ma[j-1][x]=1;                             ma[j-1][x+1]=1;                             break;                           }                      }             }             else if(id==2)             {                 int pos=10;                 for(int j=1;j<=10;j++)                 {                         if(ma[j][x]==1||ma[j-1][x]==1||ma[j][x+1]==1||ma[j][x+2]==1)                         {                             pos=j;break;                         }                 }                 ///j为行，横着的                 //x代表列                     for(int j=pos;j>=1;j--)                     {                         if(ma[j][x]==0&&ma[j-1][x]==0&&ma[j][x+1]==0&&ma[j][x+2]==0)                         {                             ma[j][x]=1;ma[j-1][x]=1;ma[j][x+1]=1;ma[j][x+2]=1;                             break;                         }                     }             }             else if(id==3)             {                 int pos=10;                 for(int j=1;j<=10;j++)                 {                         if(ma[j][x]==1||ma[j][x+1]==1||ma[j][x+2]==1||ma[j][x+3]==1)                         {                             pos=j;break;                         }                 }                 ///j为行，横着的                 //x代表列                     for(int j=pos;j>=1;j--)                     {                         if(ma[j][x]==0&&ma[j][x+1]==0&&ma[j][x+2]==0&&ma[j][x+3]==0)                         {                             ma[j][x]=1;ma[j][x+1]=1;ma[j][x+2]=1;ma[j][x+3]=1;                             break;                         }                     }             }             else if(id==4)             {                 int pos=10;                 for(int j=1;j<=10;j++)                 {                     if(ma[j][x]==1||ma[j][x+1]==1||ma[j-1][x+1]==1||ma[j][x+2]==1)                         {                             pos=j;                             break;                         }                                       }                     for(int j=pos;j>=1;j--)                     {                         if(ma[j][x]==0&&ma[j][x+1]==0&&ma[j-1][x+1]==0&&ma[j][x+2]==0)                         {                             ma[j][x]=1;ma[j][x+1]=1;ma[j-1][x+1]=1;ma[j][x+2]=1;                             break;                         }                     }             }         }     for(int i=1;i<=10;i++)         {             for(int j=1;j<=10;j++)                 cout<<ma[i][j]<<' ';             cout<<endl;           } return 0; }

真的是签到题

嗯…真的是签到题

 #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5; typedef long long LL;  int main(void) {      cout<<"NUC2020!!!"<<endl         <<"NUC2020!!!"<<endl         <<"NUC2020!!!"<<endl;  return 0; } 

港口

题意：算法竞赛进阶指南增减序列原题

书上的解释：

/*给定一个长度为n的数列(n<1e5),每次可选择一个区间{l,r}，使下标在这个区间内的数都加1或者都减1。求至少需
要多少次操作才能使数列中所有数一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
求出 a的差分数列b b1=a1,bi=ai-ai-1 令bn+1=0。 题目对序列a的操作相当于每次选出b2~bn+1的任意两个数，一
个加1，一个减1。目标是把 b2~bn全部变为0，最终的得到的数列是由n个a1构成的。
选b可以分为四类
1.选bi和bj  2<=i,j<=n; 这种操作会改变b2~bn中两个数的值，应该保证在一正一负的前提下，尽量多地采取这种操
作，更快接近目标。
2.选b1 和bj 2<=j<=n;
3.选bi和bn+1；
4.选b1和bn+1 这种情况没有意义，因为他不会改变b2~bn的值，相当于浪费了一次操作，一定不会是最优解。
分析：
设b2~bn中正数总和是p，复数的绝对值总和的绝对值是q。首先以正负数配对的方式尽量多执行第一类操作，可执行
min(p,q)次，剩余|p-q|个未配对，每个可以选择与b1和bn配对，即执行第2或3类操作，共需|p-q|次。
综上所述：最少操作次数为min(p,q)+|p-q|=max(p,q)次，根据|p-q|次第2，3类操作的选择情况，能产生|p-q|+1种不同的b1
的值，即最终得到的序列a可能有|p-q|+1种。 */

个人思考：对一段区间++/–的操作，转化到差分。比如 a[l ~r]++,我们只要让b[l]++,b[r+1]–就行了。这两个操作是等价的。于是我们要让a[1~n]里面的高度都相等，只要让b[2 ~ n]的值都为0。那么b[2~n]的值有正有负。我们只要知道b[2—n]里的正的和负的的和（注意负的要取和的绝对值）最大是多少就行了。

简单的线性代数

 #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e4+10; typedef long long LL; LL a[maxn][maxn]; int main(void) {  LL n, k;  cin>>n>>k;  for(LL i=1;i<=n;i++)   for(LL j=1;j<=n;j++)     cin>>a[i][j];  for(LL i=1;i<=n;i++)    for(LL j=1;j<=n;j++)     {      if(i==j) a[i][j]=1-a[i][j];      else a[i][j]=-1*a[i][j];     }  for(LL i=1;i<=n;i++)    {      for(LL j=1;j<=n;j++)      cout<<a[i][j]<<' ';    cout<<endl;   } return 0; } 

数位操作1

思路：对一个数10^10的数，我们按照位数来思考，对每一位进行枚举，对两个数乘积相同来说，把最大的数位上的数放到最右边，肯定能使这个数整体的大小变得最小。那么用stack进行贪心枚举。对每一位数从9-2进行枚举，看是否整除，能整除的话放到stack里，最后逆序输出。

像这种数字特别大的考虑每一位的枚举就会变小..

注意：当n=1~9时，11，12，13….19是满足的，特判

 #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> #include<stack>  using namespace std; const int maxn=1e5; typedef long long LL;  int main(void) {   LL n;   while(cin>>n)   {    if(n<=9)    {     cout<<1<<n<<endl;    continue;    }   stack<int> q;    ///注意for放在外面达到最大贪心    for(int i=9;i>=2;i--)   {    while(n%i==0)    {     n/=i;     q.push(i);    }   }   if(n>9)   {    cout<<"-1"<<endl;    }    else   {    while(q.size())    {     int p=q.top();q.pop();     cout<<p;    }    cout<<endl;   }   }  return 0; } 

签个到

链接：https://ac.nowcoder.com/acm/contest/5188/K
来源：牛客网

给定 n n n个正整数：a1,a2…an−1,ana_1,a_2…a_{n-1},a_na1​,a2​…an−1​,an​,每次操作可以选择数组中任意一个数加上或减去其下标。(即ai=ai+ia_i=a_i+iai​=ai​+i或ai=ai−ia_i=a_i-iai​=ai​−i)
求 m m m次操作后，数组中最大值与最小值的差最大可能是多少。 (数组下标从1开始）

输入描述:

 第一行输入整数 n n n和 m m m。 (1<=n<=100000,0<=m<=100000) (1<=n<=100000,0<=m<=100000) (1<=n<=100000,0<=m<=100000) 接下来一行输入 n n n个整数，第 i i i个数代表aia_iai​。(−100000<=ai<=100000)(-100000<=a_i<=100000)(−100000<=ai​<=100000) 

输出描述:

 输出一个整数，表示执行完所有操作后最大值和最小值的差可能的最大值。

示例1

输入

复制 2 1 2 1

 2 1 2 1

输出

复制 3

 3

说明

 进行一次操作a2−2=−1a_2-2=-1a2​−2=−1,使得最大值是 2 2 2，最小值是 −1 -1 −1，答案为 3 3 3。

思考：看到题知道是贪心，但是自己贪心过头了。

假如有一堆数，m=1,那么我们操作的时候，应该是对最优(先别管什么是最优的）的两个数进行操作。那么当m扩大，我们依然对这两个最优的数进行多次m的操作，结果肯定是最优的。

那我之前wa的时候就是对这两个数进行了贪心处理。但是是有反例的。比如贪心出的最大和最小和是一个数之类的balbala

那么我们发现，答案会存在两个情况下：一个是，最大值-（某个数-i*m)；第二个是,(一个数+i*m)-最小值。

那么对于“一个数”我们枚举求最优的就行了

 #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5+10; typedef long long LL; LL a[maxn]; LL b[maxn]; int main(void) {  LL n,m;cin>>n>>m;    for(LL i=1;i<=n;i++) {cin>>a[i];b[i]=a[i]; }  if(n==1) cout<<"0"<<endl;  else   {   sort(a+1,a+1+n);   LL a_max=a[n];LL a_min=a[1];   LL ans1=-0x3f3f3f3f;   LL ans2=0x3f3f3f3f;   //一个数+i*m-最小值    for(LL i=1;i<=n;i++)   {    ans1=max(b[i]+i*m,ans1);   }   //最大值-(一个数-i*m)    for(LL i=1;i<=n;i++)   {    ans2=min(b[i]-i*m,ans2);   }   cout<<max(ans1-a_min,a_max-ans2)<<endl;  } return 0; }