目录 按AC先后顺序
- Problem A: Adolescent Architecture(排序+思维)
- Problem F: Flip Flow(模拟)
- (*牛逼)Problem M: Mixtape Management(构造+思维)
- Problem L: Lexicographical Lecturing(水题,暴力+优化)
- Problem K: Knightly Knowledge(离散+贪心)
Problem A: Adolescent Architecture(排序+思维)
题意
输入
给你n个(正方体积木或者圆住积木),
让你一层放一个 下面n行 一个string表示(正方体or圆柱体),
一个int表示该方块的半径or边长
条件限制:
摆出来的积木形状必须是塔的形状
允许轮廓相交
输出
如果不可行输出 impossible
否则 从上到下输出 string 和 int
思路分析
因为是塔 所以我们需要对这个数组进行排序
如果遇到了圆柱体 那么我们就分两种情况判断
一种是 圆柱体+ 正方体
一种是 圆柱体+圆柱体
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double q2 = 1.414;
const int N = 110;
int n;
struct node
{
double a;
int op;
} num[N];
bool cmp(node x,node y )
{
if(x.a==y.a)
return x.op<y.op;
return x.a<y.a;
}
int main()
{
cin>>n;
double x;
string s;
for(int i=1; i<=n; i++)
{
cin>>s;
cin>>x;
if(s == "cube")
{
num[i].a = x;
num[i].op = 1;
}
else
{
num[i].a = x*2;
num[i].op = 0;
}
}
sort(num+1,num+1+n,cmp);
for(int i = n;i>=2;i -- )
{
if(num[i].op == 0 && num[i-1].op == 1)
{
double pd = num[i-1].a *q2 ;
if(pd>num[i].a)
{
cout<<"impossible";
return 0;
}
}
if(num[i].op ==0 && num[i-1].op == 0)
{
if(num[i].a >num[i-1].a)
{
cout<<"impossible";
return 0;
}
}
}
for(int i=1; i<=n; i++)
{
if(num[i].op == 1)
{
cout<<"cube"<< " "<<num[i].a<<endl;
}
else
{
cout<<"cylinder"<<" "<<(int)num[i].a/2<<endl;
}
}
return 0;
}
总结
这题还是A慢了, 1个半小时才A出来
主要还是单词认不出来,影响到了思路分析,(圆柱体cylinder 正方体cube)
Problem F: Flip Flow(模拟)
输入
给你一个沙漏,沙漏中有 s个沙子(一个沙子代表1s),问从t时间开始计时 沙子什么时候漏完
t s n ,n表示在什么时间 沙漏反转
沙漏在0s的状态还未开始漏
输出
输出从t开始之后多久漏完
思路分析
直接走模拟即可
总结
emm 签到题,但是英语量也挺多的,还真卡在A题 都没跑这道题了
code:
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int t,s,n;
cin>>t>>s>>n;
int a[1005];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int up,down;
down=s;
int k=1;
for(int i=1;i<=t;i++)
{
if(up>0)
{
up--;
down++;
}
if(i==a[k])
{
swap(up,down);
k++;
}
}
int ans=up;
cout<<up<<endl;
return 0;
}
(*牛逼)Problem M: Mixtape Management(构造+思维)
输入
给你一个 n 表示p的全排列的长度
下面p(1~n)
条件限制:
输出的数需要满足字典序
且第i个数 要是 第p[i]个小的数
输出:
输出满足条件的序列
思路分析
这题想了挺久,一开始我还把正确思路的方向给否定了
因为需要构造字典序,所以我们贪心地想 1 12 123 1234 12345 这种如何满足第二条件
经过贪心的再贪心,发现我们只需要在 第一个小的数的位数上多添几个0即可
这样就满足了p[i]个小的数
总结
第一次碰到这种构造题,有点自乱阵脚的感觉,但是和队友讨论之后,加上自己的思考发现还是愚人自愚了
code:
const int N = 110;
int p[N];
int n;
struct node
{
string s;
}ans[N];
int main()
{
cin>>n;
int maxn = 0 ;
int idx = 0;
for(int i=1; i<=n; i++)
{
cin>>p[i];
maxn = max(p[i],maxn);
if(p[i] == 1)
idx = i;
}
for(int i=1;i<=n;i++)
{
int id = 0;
for(int j=1;j<=i%10;j++)
{
ans[i].s+=('0'+j);
id++;
}
for(int j=1;j<=(idx+(p[i]-id));j++)
ans[i].s+='0';
}
for(int i=1;i<=n;i++)
cout<<ans[i].s<<" ";
return 0;
}
Problem L: Lexicographical Lecturing(水题,暴力+优化)
输入
输入n(那个字符串),m(每个字符串的长度)
下面n行按照字典序给出的字符串
问所有字符串的公共最小不相等子串
输出
输出子串的L和R
思路分析:
分析数据范围 n<=500, m<=2e4(210^4)
暴力做法 nm 也就是10^7 有点玄乎但是没关系,我们分两边来搞即可
总结
题目一定要放大来看,不要一半题目一半IDE界面,搞得我把2e4看成2e5想了挺久的算法
code:
int main()
{
read(n),read(m);
for(int i=1; i<=n; i++)
cin>>s[i];
int idx = 0;
for(int i=0; i<=m; i++)
{
bool flag = false;
for(int j = 1; j<=n; j++)
{
if(s[1][i]!=s[j][i])
{
idx = i;
flag =true;
break;
}
}
if(flag)
break;
}
int r = 0;
for(int i=m-1; i>=0; i++)
{
bool flag = false;
for(int j = 1; j<=n; j++)
{
if(s[1][i]!=s[j][i])
{
r = i;
flag =true;
break;
}
}
if(flag)
break;
}
cout<<idx+1<<" "<<r+1;
return 0;
}
Problem K: Knightly Knowledge(离散+贪心)
输入
给你一个n和m ,
n表示教堂的数量,m表示石碑是数量
下面n行输入教堂的x y
下面m行输入教堂的x y
条件:
对于每个石碑所在的X和Y 都会有一个直线
如果一个教堂被两个直线所经过 那么这个教堂被称为强大教堂
只允许你放置一个石碑
输出
放置的石碑的x和y
输出最大能变成的强化教堂数量
思路分析:
因为我们的坐标存在负数 所以我们需要用map来处理
然后我们贪心的找 只有一条直线经过的教堂
最后我们枚举一下最大值即可
总结:
做题要想清楚什么是可以通过某些量直接变化过来的
因为没有搞懂石碑的x和y到底怎么来 所以想了挺久
但是最后发现我们只需要通过两个直线的交线就可以确定石碑的xy了所以就没必要考虑怎么来的了
code
int n,m;
map<int,int> mx;
map<int,int> my;
map<int,int> sx;
map<int,int> sy;
int main()
{
cin>>n>>m;
int ans = m;
while(n -- )
{
int x,y;
cin>>x>>y;
mx[x] ++;
my[y] ++;
}
while(m -- )
{
int x,y;
cin>>x>>y;
if(mx[x]<2 && my[y]<2)
{
sx[x] ++;
sy[y] ++;
}
}
map<int,int>::iterator it;
map<int,int>::iterator it2;
int maxn = 0;
int ansx,ansy;
for(it=sx.begin(); it!=sx.end(); it++)
{
for(it2=sy.begin(); it2!=sy.end(); it2++)
{
if(mx[it->first] >=1 &&my[it2->first]>=1)
{
int sum =sx[it->first]+ sy[it2->first];
if(maxn < sum)
{
maxn = sum;
ansx = it->first;
ansy = it2->first;
}
}
}
}
cout<<ansx<<" "<<ansy<<endl;
cout<<maxn;
return 0;
}