寒假训练第三周
第一天
牛客训练营第一期
E.鸡算几何
大意：
L型铁丝AB-BC，
操作1是任意平移
操作2是绕B点任意旋转
操作3是在三维空间里任意调整铁丝位置
给出铁丝前后坐标，问是否一定需要操作3
思路：
只有铁丝进行了翻转操作才必须要操作3
用叉乘来判断相对位置
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
struct point{
double x;double y;
}a,b,c,d;
double x1,x2,x3,y11,y2,y3;
int n,m;
double dd(point x){
return sqrt(x.x*x.x+x.y*x.y);
}
double cross(point a,point b){
return a.x*b.y-b.x*a.y;
}
int main()
{
int t;
cin>>t;
while (t--){
cin>>x1>>y11>>x2>>y2>>x3>>y3;
a={x1-x2,y11-y2};
b={x3-x2,y3-y2};
cin>>x1>>y11>>x2>>y2>>x3>>y3;
c={x1-x2,y11-y2};
d={x3-x2,y3-y2};
if(fabs(dd(a)-dd(c))>1e-5)swap(c,d);
if(fabs(dd(a)-dd(b))<1e-5){
cout<<"NO"<<endl;
continue;
}else if(fabs(cross(a,b)-cross(c,d))>1e-5){
cout<<"YES"<<endl;
continue;
}else cout<<"NO"<<endl;
}
return 0;
}
M.本题主要考察了找规律
大意：
m个仙贝分给n个朋友
被分到的朋友的好感度为：分到的仙贝/（当前次还为分）所有仙贝
问最多能收获多少好感度
思路：
dp
f[i][j],i为朋友编号，j为剩下的仙贝数，再来个k为分给一个朋友的仙贝数
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main()
{
int n,m;
cin>>n>>m;
vector<vector<double>> f(n+1,vector<double>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k]+1.0*k/(m-j+k));
}
}
}
cout<<fixed<<setprecision(9)<<f[n][m];
return 0;
}
第二天
洛谷每日一题
A.Go Home
大意：
袋鼠跳跃步数随秒数递增
每秒可选跳或不跳
问最少在第几秒钟到家
思路：
找规律
n*(n+1)/2
n和n+1之间的步数和n+1相同
前一步不走就好了
代码：
#include <bits/stdc++.h>using namespace std;
#define ll long long#define endl '\n'const ll N=1e5+10;
int main(){
ll n;
cin>>n;
ll tem=0;
for(ll i=1;i<=n;i++){
tem+=i;
if(n<=tem){
cout<<i;
break;
}
}
return 0;
}
第三天
cf排位赛
G.Red Black Tree
大意：
n层，第几层就有几个叶子，
若一个叶子为黑色，则它下面的两个叶子也要是黑色，
若两个相邻叶子是黑色，则它们上面的那个叶子也要是黑色，
给出黑色叶子的坐标，问树上最后有几个黑色叶子
思路：
三角形融合
y-x+n为1个点辐射到第n层后最右边的那个点的位置
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
#define int long long
struct node
{
int l,r;
}a[maxn];
bool cmp(node x,node y)
{
return x.l<y.l;
}
int n,k;
signed main ()
{
cin>>n>>k;
for (int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
a[i].l=y;
a[i].r=y-x+n;
}
sort(a+1,a+1+k,cmp);
int l=a[1].l,r=a[1].r;
int ans=0;
for (int i=2;i<=k;i++)
{
int tl=a[i].l;
int tr=a[i].r;
if (tl<=r+1)
{
r=max(r,tr);
}
else
{
ans+=(r-l+1+1)*(r-l+1)/2;
l=a[i].l,r=a[i].r;
}
}
ans+=(r-l+1+1)*(r-l+1)/2;
cout<<ans<<'\n';
}
K.Bit
大意：
给出与、或、异或3种操作，
m次和操作数，
给定q个右边界，
问在边界内使最后结果最大的数
思路：
二进制数的位操作是独立的，
可贪心每一位取0或1，
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e5+10;
const ll mod=1e9+7;
ll n,q,f0=0,f1=0x7fffffff;
int main()
{
cin>>n>>q;
while (n--){
ll op,a;
cin>>op>>a;
if(op==1){
f0&=a;
f1&=a;
}else if(op==2){
f0|=a;
f1|=a;
}else if(op==3){
f0^=a;
f1^=a;
}
}
while(q--){
ll r;
cin>>r;
ll p=log2(r);
ll ans=0;
for(ll i=(1<<p);i;i>>=1){
if((ans+i)<=r&&((f1&i)>(f0&i)))ans+=i;
}
cout<<ans<<endl;
}
return 0;
}
K.Beautiful String
大意：
给定一个字符串s，
并规定范围是‘a'到'r',
规定字符串t，
要么t中所有字母s中出现
要么t中第1个字母在中出现，并升序排列，
要求t中每个字母都不同且规定t的长度
问这样的字符串有几个
思路：
排列组合
记录原字符串的字母种数，并标记，
升序排列意味着任取m个，只会有1种情况
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 18;
int cnt[N], n, m;
LL jie[20];
LL C(int n, int m){
if (n < m || n < 0 || m < 0)
return 0;
return jie[n] / jie[m] / jie[n - m];
}
LL A(int n, int m){
if (n < m || n < 0 || m < 0)
return 0;
return jie[n] / jie[n - m];
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
jie[0] = 1;
for(int i=1;i<=N;i++){
jie[i]=jie[i-1]*i;
}
int t;
cin >> t;
while(t--){
string s;
cin >> s >> n;
for(auto &i : s)
cnt[i - 'a'] ++;
LL tmp = 0;
int cc = 0;
for(int i = 0; i < N; ++ i)
if (cnt[i] != 0){
++ cc;
tmp += C(18 - i - 1, n - 1);
}
tmp -= C(cc, n);
tmp += A(cc, n);
cout << tmp << '\n';
for(int i = 0; i < N; ++ i)
cnt[i] = 0;
}
return 0;
}
第四天
补之前的题
D.牛牛取石子
大意：
两堆石子，一堆a个，一堆b个，
操作1：第一堆取1个，第二堆取2个
操作2：第一堆取2个，第二堆取1个，
牛牛和牛妹轮流选一个操作，
谁无法取石子谁输，问获胜者
思路：
对称博弈，
min(a,b)%3，
两堆一样再分类讨论
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while (t--){
long long a,b;
cin>>a>>b;
if(a==b){
if(a%3==0){
cout<<"niumei"<<endl;
continue;
}else if(a%3==1){
cout<<"niumei"<<endl;
}else {
cout<<"niuniu"<<endl;
}
}else{
long long mi=min(a,b);
if(mi%3==0){
cout<<"niumei"<<endl;
continue;
}else{
cout<<"niuniu"<<endl;
}
}
}
return 0;
}
第五天
牛客训练营第三期
B.勉强拼凑的记忆
大意：
用恰好n块矩形积木搭建正方形，
积木大小为1* k，1<=k<=n/2（向上取整），
问搭成的最大正方形的边长。
思路：
尽量用长为n/2的搭建，
式子：3ans-2（n/2)向上取整<=n
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const ll mod=1e9+7;
int main()
{
int t;
cin>>t;
while (t--){
ll n;
cin>>n;
if(n==2){
cout<<-1<<endl;
continue;
}
ll tem;
if(n&1) tem=n+1;
else tem=n;
cout<<(n+2*(tem/2))/3<<endl;
}
return 0;
}
E.公平守望的灯塔
大意：
给定A,B两点坐标，
求使三角形ABC为等腰直角三角形的C点坐标，要求AB为斜边
思路：
向量，
两个全等三角形
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const ll mod=1e9+7;
int main()
{
ll xa,ya,xb,yb;
cin>>xa>>ya>>xb>>yb;
xa*=2;ya*=2;xb*=2;yb*=2;
ll xm=(xa+xb)/2,ym=(ya+yb)/2;
ll dx=xm-xa,dy=ym-ya;
if((xm+dy)%2==0&&(ym-dx)%2==0){
cout<<(xm+dy)/2<<' '<<(ym-dx)/2;
}else cout<<"No Answer!";
return 0;
}