a.亲密数对
题很简单，要注意两个数都不能超过n的范围
b.吉祥数
由于n<8就暴力做，要注意要把所有的新数算出来再淘汰
c.二叉树输出
题意就是构造好树后，再先序遍历
#include<bits/stdc++.h>
using namespace std;
struct tir {
char q;
int num;
tir *lc;
tir *rc;
};
int i=0;
inline void pr(tir *p,string a,string b,int x,int y) {
if(i<b.length()) {
p->q=a[i];
p->num=0;
p->lc=new tir;
p->rc=new tir;
int u=i,k=b.find(a[i]);
if(k-1!=x){
i++;
pr(p->lc,a,b,x,k);
p->num=p->lc->num;
} else {
p->lc=NULL;
}
if(k+1!=y){
i++;
pr(p->rc,a,b,k,y);
p->num+=p->rc->num;
} else {
p->rc=NULL;
}
if(p->num==0) p->num=1;
}
}
inline void po(tir *p) {
if(p!=NULL) {
for(int i=1;i<=p->num;i++) cout<<p->q;
cout<<endl;
po(p->lc);
po(p->rc);
}
}
int main() {
string a,b;
cin>>a>>b;
tir *p=new tir;
p->lc=NULL;
p->rc=NULL;
int y=b.length(),x=-1;
pr(p,a,b,x,y);
po(p);
return 0;
}
/*
abdec
dbeac
*/d.关系网络
弗洛伊德板题
e.fib的Sn
一开始是根据公式用等比数列求和得出的 Sn 就等于
-1 然后用矩阵乘法就可以了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod;
ll n,f[2],a[2][2];
void mul(ll f[2],ll a[2][2]) {
ll c[2];
memset(c,0,sizeof(c));
for(int j=0; j<2; j++)
for(int k=0; k<2; k++)
c[j]=(c[j]+f[k]*a[k][j]%mod)%mod;
memcpy(f,c,sizeof(c));
}
void mulself(ll a[2][2]) {
ll c[2][2];
memset(c,0,sizeof(c));
for(int i=0; i<2; i++)
for(int j=0; j<2; j++)
for(int k=0; k<2; k++)
c[i][j]=(c[i][j]+a[i][k]*a[k][j]%mod)%mod;
memcpy(a,c,sizeof(c));
}
int main() {
cin>>n>>mod;
n+=2;
ll f[2]= {0,1};
ll a[2][2]= {{0,1},{1,1}};
for(; n; n>>=1) {
if(n&1) mul(f,a);
mulself(a);
}
f[0]--;
f[0]+=mod;
f[0]%=mod;
cout<<f[0];
}
/*
2000000000 1000000010
*/f.三角形
显然，总体思路应为：【三角形数量】等于【任选三个点的方案数】减去【三点共线的方案数】。
共有 (n+1)(m+1) 个点，故【任选三个点的方案数】为
【三点共线的方案数】等于【横着的】加【竖着的】加【斜着的】。
【横着的】指三点所在直线平行于 x 轴。共有 m+1 条横线，每条横线上有 n+1 个点，从这 n+1个点中选取 3个，方案数为
同理，【竖着的】指三点所在直线平行于 y 轴，方案数为
看来，我们现在最关心的是【斜着的】，斜着的直线按斜率正负分为两种，并且这两种的方案数是相等的。因此，我们只需要计算出斜率为正的方案数ans，再乘以 2 即可。
开longlong就可以过
g.加工生产调度
贪心
#include<bits/stdc++.h>
using namespace std;
struct node {
int d,a,b,k;
bool operator<(const node &x)const{
if(d==x.d){
if(d<=0)return a<x.a;
else return b>x.b;
}
return d<x.d;
}
}c[40001];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i].a;
c[i].k=i;
}
for(int i=1;i<=n;i++){
cin>>c[i].b;
if(c[i].a<c[i].b) c[i].d=-1;
if(c[i].a==c[i].b) c[i].d=0;
if(c[i].a>c[i].b) c[i].d=1;
}
sort(c+1,c+n+1);
int fa=c[1].a,fb=c[1].a+c[1].b;
for(int i=2;i<=n;++i){
fb=max(fa+c[i].a,fb)+c[i].b;
fa+=c[i].a;
}
cout<<max(fa,fb)<<endl;
for(int i=1;i<=n;i++){
cout<<c[i].k<<" ";
}
return 0;
}
h.灯泡
数学题 注意分类讨论
#include<bits/stdc++.h>
using namespace std;
double H,h,D;
int main(){
int T;
cin>>T;
while(T--){
cin>>H>>h>>D;
double a=sqrt((H-h)*D);
double b=D*(H-h)/H;
if(a<=b){
printf("%.3lf\n",D-(H-h)*D/H);
} else if(a<=D){
printf("%.3lf\n",D+H-2*a);
} else {
printf("%.3lf\n",h);
}
}
}