AI弱鸡

1085

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
long long int n;
cin>>n;
cout<<n<<' ';
while(n)
{
n = n/2;
if(n > 1)
cout<<n<<' ';
else if(n == 1)
{
cout<<n<<endl;
break;
}
else break;
}
return 0;
}


AI弱鸡
11天前

# 字符串的相关操作

## 初始化

char str1[] = {"Le Chapon Dodu"};
string str2 = {"Le Chapon Dodu"};
char str3[20] = "jinan";


## 赋值，拼接和附加


char charr1[20];
char charr2[20] = "jinan";
//赋值操作
charr1 = charr2;

string str2 = {"Le Chapon Dodu"};
string str3 = {"Le Dodu"};
str3 = str3 + str2;


# 结构体

//申请结构体
stuct tree
{
int l;
int r;
double k;
}

//申请结构体数组
struct tree a[50];

//初始化结构体
tree b = {1,2,1.0};
a[0] = b;


# vector

#include<vector>

vector<int> v;

//把1压入堆栈
v.push_back(1);

//返回首尾元素
int a = v.begain();
int b = v.end();

//返回v的大小
v.size();

//判断是否为空
v.empty();


AI弱鸡
13天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10,M = N*2;
typedef long long LL;
int n;
int w[N];
int h[N],e[M],ne[M],idx;
LL f[N];

{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int u,int father)
{
f[u] = w[u];
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(j != father)
{
dfs(j,u);
LL zero = 0;
f[u] += max(zero,f[j]);
}
}
}
int main()
{
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i = 1;i<=n;i++) scanf("%d",&w[i]);
int a,b;
for(int i = 0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
}
dfs(1, -1);
LL res = f[1];
for(int i = 2;i<=n;i++)res = max(res,f[i]);
cout<<res<<endl;
return 0;
}


AI弱鸡
13天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 300010;
typedef long long LL;

LL a[N],s[N];
bool st[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
s[0]=0;
for(int i = 1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i] = s[i - 1] + a[i];
}
LL s0 = s[0],sn = s[n];
if(s0 >sn)swap(s0,sn);
sort(s,s + n + 1);

for(int i = 0;i<=n;i++)
{
if(s[i] == s0)
{
s0 = i;
break;
}

}
for(int i = n;i>=0;i--)
{
if(s[i] == sn)
{
sn = i;
break;
}

}
memset(st, 0, sizeof st);
int l = 0,r = n;
for(int i = s0;i>=0;i -= 2)
{
a[l++] = s[i];
st[i] = true;
}
for(int i = sn;i<=n;i += 2)
{
a[r--] = s[i];
st[i] = true;
}

for(int i = 0;i<=n;i++)
{
if(st[i] == false)
{
a[l++] = s[i];
st[i] = true;
}
}
LL res = 0;

for(int i = 1;i<=n;i++)res = max(res,abs(a[i] - a[i - 1]));

printf("%lld\n", res);
}
return 0;
}



AI弱鸡
14天前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010,MOD = 1000000009;
int a[N],b[N];
long long int res = 1;
int n,k;

//a存整数，b存负数

int main()
{
int w = 0,e = 0,z = 0,num;
cin>>n>>k;
//w表示正数个数，e表示负数个数
if(n == k)
{
for(int i = 0;i<n;i++)
{
scanf("%d",&num);
res = (res*num)%MOD;
}
cout<<res<<endl;
return 0;
}
for(int i = 0;i<n;i++)
{
scanf("%d",&num);
if(num>0) a[++w]=num;
else if(num<0) b[++e]=num;
else  z = 1;

}
sort(a+1,a+w+1);
sort(b+1,b+e+1);
if(k%2 == 1&& w == 0)
{
if(z == 0)
{
for(int i = 0;i<k;i++)res = 0 - (0 - res*b[e - i])%MOD;
}
else res = 0;
cout<<res<<endl;
return 0;
}
else
{
int flag = 1;
if(k%2 == 1)
{
res = a[w--];
k--;
}
while(flag<= e - 1 && w>1 && k)
{
long long int num1 = (long long int) a[w]*a[w - 1];
long long int num2 =  (long long int) b[flag]*b[flag + 1];
if(num1> num2)
{
res = (((res* a[w])%MOD)*a[w - 1])%MOD;
w = w - 2;
}
else
{
res = 0 - (0 - res*b[flag])%MOD;
res = 0 - (0 - res*b[flag + 1])%MOD;
flag = flag + 2;
}
k = k - 2;
}
if(k)
{
if(flag>e - 1)
{
for(int i = k;i>=1;i--)
{
res = (res* a[w])%MOD;
w --;
}
}
else
for(int i = k;i>=1;i--)
{
res = 0 - (0 - res*b[flag])%MOD;
flag++;
}
}
}
cout<<res<<endl;
return 0;
}


AI弱鸡
14天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 2*1e5 + 10;
int s[N];
long long int res = 0;
int main()
{
int n,m;
cin>>n>>m;
for(int i = 0;i<n+m+1;i++)scanf("%d",&s[i]);
sort(s,s+n+m+1);
if(!m)
for(int i = 0;i<n+m+1;i++)res += s[i];
else
{
res = s[n+m] - s[0];
for(int i = 1;i<n+m;i++)res += abs(s[i]);
}
printf("%lld",res);
return 0;
}


AI弱鸡
15天前

# 枚举

## 递归实现指数型枚举

const int N=15;
int n;
int st[N];
void dfs(int u)
{
if(u>=n)
{
for(int i=0;i<=n;i++)
{
if(st[i]==1)printf("%d ",(i+1));
}
printf("\n");
return;
}
st[u]=1;
dfs(u+1);

st[u]=2;
dfs(u+1);
st[u]=0;
}


## 递归实现排列型枚举

const int N=10;
int n;
int state[N];//表示没用过，1~N表示数字
bool used[N];//true表示用过，false表示没用过

void dfs(int num)
{
if(num>n)
{
for(int i=1;i<=n;i++) printf("%d ",state[i]);
puts(" ");

return;
}
for(int i=1;i<=n;i++)
{
if(!used[i])
{
used[i]=true;
state[num]=i;
dfs(num+1);

state[num]=0;
used[i]=false;
}
}
}


## 递归实现组合型枚举

const int N=30;
int n,m;
int way[N];
void dfs(int u,int start)
{
if(u==m+1)
{
for(int i=1;i<=m;i++)printf("%d ",way[i]);
puts("");
return;
}
for(int i=start;i<=n;i++)
{
way[u]=i;
dfs(u+1,i+1);
}
}



# 二分法

## 整数的二分法


// n 是数组的中元素的个数
// k为要查找的数
//输出为该元素的起始位置与终止位置
int l = 0, r = n -1;
int k;
scanf(“%d”,&k);
while(l < r)
{
int mid = l + r >> 1;
if(m[mid] >= k)r = mid;
else l = mid + 1;
}

    if(m[l] != k) printf("-1 -1\n");
else
{
cout << l << ' ';

int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(m[mid] <= k)l = mid;
else r = mid - 1;
}
cout<<l<<endl;
}




## double类型的二分法

 while(r-l>1e-8)
{
mid = (l + r)/2;
if(mid*mid*mid > n)r = mid;
else l = mid;
}


# 前缀和

## 一维前缀和

1，初始化数组

    for(int i = 1;i <= n;i++)
{
s[i] +=s[i-1];
}


2, 求和

    while(m--)
{
res = s[r]-s[l-1];
}


## 二维数组前缀和

1，初始化数组

    for(int i = 1;i <=n;i++)
for(int j = 1;j <=m;j++)
{
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}


2, 求和

   for(int i =0;i<q;i++)
{
res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
cout<<res<<endl;
}


# 双指针算法

for(int i = 0,j = 0;i < n;i++)
{
while()
{
j++;
}
}


# DFS

dfs()
{
if(到达终点状态)
{
...//根据题意添加
return;
}
if(越界或者是不合法状态)
return;
if(特殊状态)//剪枝
return ;
for(扩展方式)
{
if(扩展方式所达到状态合法)
{
修改操作;//根据题意来添加
标记；
dfs（）；
(还原标记)；
//是否还原标记根据题意
//如果加上（还原标记）就是 回溯法
}

}
}


# BFS

void bfs ()
{
queue 初始化

while(hh <= tt)  //队列非空
{
t = q[hh ++ ];  //更新队头

// 扩展队头 + 放入队列
}
}


# 欧几里得算法

int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}


# 预处理质数

void get_primes(int n)  //预处理质数
{
for(int i = 2;i<=n;i++)
{
if(!st[i])
{
minp[i] = i;
primes[cnt++] = i;
}

for(int j = 0;primes[j]*i<= n;j++)
{
int t =primes[j]*i;
st[t] =true;
minp[t] = primes[j];
if(i%primes[j]==0)break;
}
}
}


AI弱鸡
15天前

# 静态链表

int head,e[N],ne[N],idx;
//e[N]记录每个单链表的值
//ne[N]记录每个链表next指针
//idx 记录总共值的个数

//初始化单链表
void init()
{
}

//在头结点加入一个值
{
}

//表示在第k个输入的数后面插入一个数x
{
e[idx] = x,ne[idx]=ne[k],ne[k]=idx++;
}

//表示删除第k个输入的数后面的数
void remove(int k)
{
ne[k] = ne[ne[k]];
}

//遍历链表的方法
for(int i = head;i!= - 1;i = ne[i])cout <<e[i]<<' ';
cout<<endl;



# 静态链表记录树和图

const int N = 100010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

//主函数初始化过程
//其中a和b表示两点之间有一条边
memset(h, -1, sizeof h);

for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
}



# 线段树和树状数组

## 树状数组

https://www.acwing.com/solution/content/7526/
1、lowbit(x):返回x的最后一位1

int lowbit(int x)
{
return x&-x;
}


2、add(x,v):在x位置加上v，并将后面相关联的位置也加上v

void add(int x,int v)
{
for(int i = x;i<=n;i +=lowbit(i)) tr[i] +=v;
}



3、query(x):询问x的前缀和

int query(int x)
{
int res = 0;
for(int i = x;i;i-=lowbit(i)) res += tr[i];
return res;
}


## 线段树

1、pushup(u):用子节点信息来更新当前节点信息（把信息往上传递）

void pushup(int u)
{
tr[u].maxv = max(tr[u<<1].maxv , tr[u<<1|1].maxv);
}



2、build(u,l,r):在一段区间上初始化线段树，其中u表示根结点，l表示左边界，r表示右边界

void build(int u ,int l,int r)
{
if(l == r)tr[u]={l,r,w[r]};
else
{
tr[u] = {l,r};
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}


3、query(u,l,r):查询某段区间的和，其中u表示根结点，l表示左边界，r表示右边界

int query(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r)return tr[u].maxv;
int res = INT_MIN;
int mid = tr[u].l + tr[u].r >> 1;
if(mid>=l)res = query(u<<1,l,r);
if(mid<r)res = max(res,query(u<<1|1,l,r));
return res;
}


4、modify(u,x,v):修改操作，在u结点中，x位置加上v

   void modify(int u,int x,int v)
{
if(tr[u].l == tr[u].r) tr[u].sum += v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1,x,v);
else modify(u << 1 | 1,x,v);
pushup(u);
}
}


# 堆

1. 堆中某个节点的值总是不大于或不小于其父节点的值；
2.堆总是一棵完全二叉树。
3.将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

## 堆的up和down操作

down

void down(int u)
{

int t = u ;
if(2*u <= cnt && h[2*u]<h[t]) t = 2*u;
if(2*u + 1 <=cnt && h[2*u+1]<h[t]) t =2*u + 1;

if(t != u)
{
swap(h[t],h[u]);
down(t);
}
}


up

void up(int u)
{
while(u/2 && h[u/2] > h[u])
{
swap(h[u/2],h[u]);
u /= 2;
}
}


## 堆的五个基本操作

1.插入一个数

heap[++size] = x;up(size);


2.求集合当中的最小(大)值

heap[1];


3.删除最小值

heap[1] = heap[size];size--;down(1);


4.删除任意一个元素

heap[k] = heap[size];size--;down(k);up(k);


5.修改任意一个操作

heap[k] = x;down(k);up[k];


AI弱鸡
16天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

void init()
{
}

{
}

{
e[idx] = x,ne[idx]=ne[k],ne[k]=idx++;
}

void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
int m;
cin>>m;
while(m--)
{
char op;
int k,x;
cin>>op;
if(op == 'H')
{
cin>>x;
}
else if(op == 'I')
{
cin>>k>>x;
}
else
{
cin>>k;
else remove(k - 1);
}
}

for(int i = head;i!= - 1;i = ne[i])cout <<e[i]<<' ';
cout<<endl;

return 0;

}


AI弱鸡
16天前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110;
char m[N][N][N];

struct Point
{
int x, y, z;
};

int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
Point q[N*N*N];
int dist[N][N][N];
int l,r,c;
int bfs(Point start,Point end)
{
memset(dist, -1, sizeof dist);
int head = 0,tail = 0;
dist[start.x][start.y][start.z] = 0;
{
for(int i = 0;i<6;i++)
{
int X = sit.x + dx[i];
int Y = sit.y + dy[i];
int Z = sit.z + dz[i];
if(X<0||X>=l||Y<0||Y>=r||Z<0||Z>=c)continue;
if(m[X][Y][Z] == '.' && dist[X][Y][Z] == -1)
{
tail++;
q[tail].x = X;
q[tail].y = Y;
q[tail].z = Z;
dist[X][Y][Z] = dist[sit.x][sit.y][sit.z] + 1;
}
if(m[X][Y][Z] == 'E')
return dist[sit.x][sit.y][sit.z] + 1;
}
}
return -1;
}
int main()
{
Point start,end;
while(scanf("%d%d%d", &l, &r, &c),l||r||c)
{
for (int i = 0; i < l; i ++ )
for (int j = 0; j < r; j ++ )
{
scanf("%s", m[i][j]);
for (int k = 0; k < c; k ++ )
{
char C = m[i][j][k];
if (C == 'S') start = {i, j, k};
else if (C == 'E') end = {i, j, k};
}
}

int res = bfs(start,end);

if(res != -1) printf("Escaped in %d minute(s).\n",res);
else printf("Trapped!\n");
}

return 0;
}
`