|
毒瘤场，题都挺变态的。一小时ac前三题（时间全花在读题上了），然后罚坐（这次的D实在太恶心人了，补题也不想补了。。。）
A. Hard Way
几何题，题目很长很吓人，其实不难。给出三角形的三个顶点，问三角形的三条边上的点是否可以和y=0连成一条直线，这条直线不能穿过三角形内部。问三角形的边上存在这样一条直线的点的总长度是多少。
样例的小数点是唬人的，答案就是整数。只有当一条边和y=0平行并且这条边对应的角在下面这种情况这条边没有直线，除此之外所有情况全有直线。
#include <bits/stdc++.h>
#define endl '\n'
#define INF 2147483647
using namespace std;
typedef long long ll;
const int N=200001;
const int mod=1e9+7;
ll a[N],b[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,i,j;
cin>>t;
while(t--)
{
ll x1,x2,x3,y1,y2,y3;
cin>>x1>>y1;
cin>>x2>>y2;
cin>>x3>>y3;
ll ans=0;
if(y1==y2&&y1!=0&&y1>y3) ans=ans+abs(x2-x1);
if(y1==y3&&y1!=0&&y1>y2) ans=ans+abs(x3-x1);
if(y3==y2&&y2!=0&&y3>y1) ans=ans+abs(x3-x2);
cout<<ans<<endl;
}
}
B. Power Walking
这道题的题目我读了二十分钟才发现漏看了个单词，这算这场比赛最大的失误了。
给出一个长度为n的数组，输出将这n个数字全部分配给k个孩子（k的大小为1-n）得到的这k个孩子不同的ai数量的和的最小值。
贪心+map判重，贪心策略就是尽量把不重复的数字分出去，把重复的数字留给同一个孩子。这样就可以保证这个孩子的不重复数字最小，也就是所有孩子的和的最小。
#include <bits/stdc++.h>
#define endl '\n'
#define INF 2147483647
using namespace std;
typedef long long ll;
const int N=300001;
const int mod=1e9+7;
ll a[N],b[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,i,j;
cin>>t;
while(t--)
{
cin>>n;
map<int,int>c;
ll ans=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
if(c[a[i]]==0)
{
ans++;
c[a[i]]++;
}
else
c[a[i]]++;
}
cout<<ans<<" ";
for(int k=2;k<=n;k++)
{
if(k<=ans) cout<<ans<<" ";
if(k>ans) cout<<k<<" ";
}
cout<<endl;
}
}
C. Great Sequence
给出大小为n的数组和倍数x，如果数组中的两个数字满足倍数x的关系那么就可以把他们组合到一起。如果数组中的一个数字在数组中找不到满足x的关系了，就要添一个数字给它组合起来，输出最少要添多少个数字才能把数组中的所有数字组合在一起。
sort+map判重，先sort一下让数组有序防止它乱组合而达不到最优的情况。然后遍历判重看看有多少需要添数字的，尽量用除法，听说乘法好多爆int被fst的，还好不关我事。。。
#include <bits/stdc++.h>
#define endl '\n'
#define INF 2147483647
using namespace std;
typedef long long ll;
const int N=200001;
const int mod=1e9+7;
ll a[N],b[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,i,j;
cin>>t;
while(t--)
{
int x;
cin>>n>>x;
map<int,int>c;
ll sum=n;
ll ans=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
if(sum==0) break;
if(a[i]%x==0)
{
int u=a[i]/x;
if(c[u]>0)
{
c[u]--;
sum=sum-2;
continue;
}
else
c[a[i]]++;
}
if(a[i]%x!=0)
c[a[i]]++;
}
cout<<sum<<endl;
}
}
.
.
最近状态慢慢回来了，希望下次也能继续上分，快变色了（祈祷 ）
还有四级今天出分了，考的还不错，希望没过的同学们下次能有个好运气
|