http://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;
}
港口
题意：算法竞赛进阶指南增减序列原题
书上的解释：
个人思考：对一段区间++/–的操作，转化到差分。比如 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;
}
