Yuzhao_Li

6756

InvolutionZ

NgAgo
ericf
DeBeDe
WinterSweet

Shinjo_Akane
usingMaster
Kole

iiiiiiire

Yuzhao_Li
29天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
cin>>n;

for (int i = 0; i < n; i ++ ) cin>>a[i];

for (int i = 0; i < n; i ++ ){
while(a[i]%2==0) a[i]/=2;
while(a[i]%3==0) a[i]/=3;
}

bool suss=true;

for (int i = 0; i < n-1; i ++ ){
if(a[i]!=a[i+1]){
suss=false;
break;
}
}

if(suss) cout<<"Yes"<<endl;
else cout<<"No"<<endl;

return 0;
}


Yuzhao_Li
29天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 200010;

typedef long long LL;

LL n,k;
LL a[N];
map<LL,LL> ff,bb;
LL f[N],b[N];

int main()
{
cin>>n>>k;

for(int i=1;i<=n;i++){
cin>>a[i];
}

for(int i=1;i<=n;i++){
f[i]+=ff[a[i]/k];
ff[a[i]]++;
}

for(int i=n;i>=1;i--){
b[i]+=bb[a[i]*k];
bb[a[i]]++;
}

LL res=0;
for(int i=2;i<n;i++) if(a[i]%k==0) res+=f[i]*b[i];

cout<<res<<endl;

return 0;
}



Yuzhao_Li
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110,M=1010;

int t,n;
bool st[M];
int info[N][M];
int a[N];

int main()
{
cin>>t;

while(t--){
cin>>n;

memset(st,false,sizeof st);
memset(info,0,sizeof info);
int m=0;
for(int i=1;i<=n;i++) cin>>a[i],st[a[i]]=true,m=max(m,a[i]);;

int x,maxx=0;
for(int i=1;i<=n;i++){
cin>>x;
info[x][a[i]]++;
maxx=max(maxx,x);
}

for(int i=1;i<=maxx;i++){
printf("%d={",i);
for(int j=1;j<M;j++){
if(st[j]&&j!=m) printf("%d=%d,",j,info[i][j]);
else if(st[j]&&j==m) printf("%d=%d",j,info[i][j]);
}
printf("}\n");
}
}

return 0;
}


Yuzhao_Li
1个月前

#### O(n^3)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int m;
int a[N];

int main()
{
scanf("%d", &n);
while (n -- ){
scanf("%d", &m);

for(int i=0;i<m;i++) scanf("%d", &a[i]);

int res=0;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
for(int k=0;k<m;k++){
if(a[i]+a[j]==a[k]) res++;
}
}
}

cout<<res<<endl;
}

return 0;
}


#### 优化O(n^2)，枚举两个，将另一个存在存在个数存下来

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int m;
int a[N];
int cnt[110];

int main()
{
scanf("%d", &n);
while (n -- ){
scanf("%d", &m);

memset(cnt,0,sizeof cnt);
for(int i=0;i<m;i++) scanf("%d", &a[i]),cnt[a[i]]++;

int res=0;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
// for(int k=0;k<m;k++){
res+=cnt[a[i]+a[j]];
// }
}
}

cout<<res<<endl;
}

return 0;
}


Yuzhao_Li
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

string str;
long long bin[40];

int main(){
bin[1]=2;
for(int i=2;i<30;i++) bin[i]=bin[i-1]*2;

while(cin>>str){
LL res=0;
reverse(str.begin(),str.end());
for(int i=0;i<str.size();i++) res=res+(LL)(bin[i+1]-1)*(str[i]-'0');

cout<<res<<endl;
}

return 0;
}


Yuzhao_Li
1个月前
#include<iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int odd[N],even[N];
int cnto,cnte;

int main(){
for(int i=0;i<10;i++){
int x;
cin>>x;

if(x%2){
odd[cnto++]=x;
}else{
even[cnte++]=x;
}
}

sort(odd,odd+cnto,greater<int>());
sort(even,even+cnte);

for(int i=0;i<cnto;i++) cout<<odd[i]<<' ';
for(int i=0;i<cnte;i++) cout<<even[i]<<' ';

return 0;
}


Yuzhao_Li
1个月前

### dfs 枚举飞机降落的顺序(枚举所有的情况)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
struct Plane{
int t,d,l;
}p[N];
bool st[N];

bool dfs(int u,int last){
if(u==n) return true;

for(int i=0;i<n;i++){
int t=p[i].t,d=p[i].d,l=p[i].l;
if(!st[i]&&t+d>=last){
st[i]=true;
if(dfs(u+1,max(last,t)+l)) return true;
st[i]=false;
}
}

return false;
}

int main()
{
int t;
scanf("%d",&t);

while(t--){
scanf("%d", &n);
for(int i=0;i<n;i++){
int t,d,l;
scanf("%d%d%d",&t,&d,&l);

p[i]={t,d,l};
}

memset(st,false,sizeof st);

if(dfs(0,0)) printf("YES\n");
else printf("NO\n");
}

return 0;
}


#### 状态压缩dp

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10,M=1<<N,INF=0x3f3f3f3f;

int T,n;
int f[M];
struct Plane{
int t,d,l;
}p[N];

int main()
{
scanf("%d", &T);

while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++){
int t,d,l;
scanf("%d%d%d",&t,&d,&l);

p[i]={t,d,l};
}

memset(f,0x3f,sizeof f);
f[0]=0;

for(int i=1;i<1<<n;i++){
for(int j=0;j<n;j++){
int t=p[j].t,d=p[j].d,l=p[j].l;
if((i>>j)&1){
int last=f[i-(1<<j)];
if(t+d>=last){
f[i]=min(f[i],max(last,t)+l);
}
}

}
}

if(f[(1<<n)-1]!=INF) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}

return 0;
}


Yuzhao_Li
1个月前

#### O(n) 开一个数组记录以当前数结尾的最长接龙序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
string str[N];
int f[N];
int cnt[10];

int main()
{
scanf("%d", &n);

str[0]="  ";
for(int i=1;i<=n;i++) cin>>str[i];

f[1]=1;
cnt[str[1][str[1].size()-1]-'0']=1;

int maxx=1;
for(int i=2;i<=n;i++){
f[i]=1;
f[i]+=cnt[str[i][0]-'0'];

cnt[(str[i][str[i].size()-1])-'0']=max(cnt[str[i][str[i].size()-1]-'0'],f[i]);
}

int res=1e7;
for(int i=1;i<=n;i++) res=min(res,n-f[i]);
cout<<res<<endl;

return 0;
}


#### 暴力 使用O(n)的复杂度转移 TLE

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
string str[N];
int f[N];

int main()
{
scanf("%d", &n);

str[0]="  ";
for(int i=1;i<=n;i++) cin>>str[i];

// for(int i=1;i<=n;i++) cout<<str[i]<<endl;

f[1]=1;
int maxx=1;
for(int i=2;i<=n;i++){
f[i]=1;
for(int j=i-1;j;j--){
if(str[j][str[j].size()-1]==str[i][0]){
f[i]=max(f[i],f[j]+1);
maxx=max(maxx,f[i]);
}
}
}

// for(int i=1;i<=n;i++) res=min(res,n-f[i]);

cout<<n-maxx<<endl;

return 0;
}


Yuzhao_Li
1个月前
#include<iostream>

using namespace std;

const int N = 1e5+10;

int n;
int primes[N],cnt;
bool st[N];

void get_prime(int n){
for(int i=2;i<n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}

int main()
{
cin>>n;

get_prime(n+1);

if(n==2||n==1) cout<<1<<endl;
else cout<<2<<endl;
for(int i=2;i<=n+1;i++){
if(!st[i]) cout<<1<<' ';
else cout<<2<<' ';
}

return 0;
}


Yuzhao_Li
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int k;
string str;

void dfs(){
if(str[k]=='#'){
k++;
return ;
}

char r=str[k++];
dfs();
cout<<r<<' ';
dfs();

}

int main(){
cin>>str;

dfs();

return 0;
}