acwing

8849

2天前
typedef pair<int,int> PII;
#define x first
#define y second

class Solution {
public:
vector<vector<char>> g;
int n,m;
vector<vector<bool>> st;
int numIslands(vector<vector<char>>& grid) {
g=grid;
n=grid.size();
m=grid[0].size();
int cnt=0;
vector<vector<bool>> st1(n+1,vector<bool>(m+1, false));
st=st1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(grid[i][j]=='1'&&!st[i][j]){
bfs(i,j);
cnt++;
}
return cnt;
}

void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
st[x][y]=true;
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0||a>=n||b<0||b>=m||g[a][b]=='0'||st[a][b]) continue;
q.push({a,b});
st[a][b]=true;
}
}
}
};


2天前
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int sz=nums.size();
vector<int> res(sz,0);
for(int i=0;i<sz;i++){
res[(i+k)%sz]=nums[i];
}
nums=res;
}
};


4天前
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& nums) {
vector<int> ji,ou,res;
for(int i:nums){
if(i%2==0){
ou.push_back(i);
}else{
ji.push_back(i);
}
}
for(int i=0;i<ou.size();i++){
res.push_back(ou[i]);
res.push_back(ji[i]);
}
return res;
}
};


4天前
class Solution {
public:
stack<char> stk;
int cnt=0;
for(int i=0;i<s.size();i++){
if(s[i]=='(') stk.push(s[i]);
else{
if(stk.size()&&stk.top()=='('&&s[i]==')') {
stk.pop();
}
else ++cnt;
}
}
return cnt + stk.size();
}
};


6天前
#include <bits/stdc++.h>
using namespace std;

const int N=10010, M=N*2;
int n;
int h[N],e[M],ne[M],idx;
int p[N];
int maxdepth=0;

int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}

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

int dfs(int u,int father){
int depth=0;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==father) continue;
depth= max(depth,dfs(j,u)+1);
}

return depth;
}

int main(){
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)p[i]=i;
int k=n;
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);

if(find(a)!=find(b)){
k--;
p[find(a)]=find(b);
}
}
vector<int> nodes;
if(k>1) printf("Error: %d components",k);
else{
for(int i=1;i<=n;i++){
int depth=dfs(i,-1);
if(depth>maxdepth){
maxdepth=depth;
nodes.clear();
nodes.push_back(i);
}
else if(depth==maxdepth)
nodes.push_back(i);
}
for(int i=0;i<nodes.size();i++)
printf("%d\n",nodes[i]);
}
return 0;
}


6天前
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,Q;
int s[N][N];

int main(){
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&s[i][j]);

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
while(Q--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
printf("%d\n",s[l2][r2]-s[l1-1][r2]-s[l2][r1-1]+s[l1-1][r1-1]);
}
return 0;
}



6天前
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],s[N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) {
s[i] = s[i-1]+a[i];
}
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n", s[r]-s[l-1]);
}
return 0;
}



6天前
// 巧妙的并查集
#include <bits/stdc++.h>
using namespace std;

const int N=1100010;

int p[N];

int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}

int main(){
int n;
scanf("%d",&n);
for(int i=1;i<N;i++)p[i]=i;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
x=find(x);
printf("%d ", x);
p[x]=x+1;
}
return 0;
}

//暴力过7个点
#include <bits/stdc++.h>
using namespace std;

unordered_map<int,int> pq;
vector<int> res;
int maxv=INT_MIN;

int main(){
int n;
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
while(pq.count(x)){
x++;
}
pq[x]++;
res.push_back(x);
}

printf("%d",res[0]);
for(int i=1;i<res.size();i++){
printf(" %d",res[i]);
}
return 0;
}


6天前
#include <bits/stdc++.h>
using namespace std;
const int N=40;
int n;
int postorder[N],inorder[N];
unordered_map<int,int> l,r,pos;
int q[N];

int build(int il,int ir,int pl,int pr){
int root=postorder[pr];
int pivot=pos[root];
if(il<pivot) l[root]=build(il,pivot-1,pl,pl+pivot-1-il);
if(pivot<ir) r[root]=build(pivot+1,ir,pl+pivot-1-il+1,pr-1);
return root;
}

void bfs(int u){
int hh=0,tt=0;
q[0]=u;
while(hh<=tt){
int t=q[hh++];
if(l.count(t)) q[++tt]=l[t];
if(r.count(t)) q[++tt]=r[t];
}
cout<<q[0];
for(int i=1;i<n;i++) cout<<' '<<q[i];
cout<<endl;
}

int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>postorder[i];
for(int i=0;i<n;i++){
cin>>inorder[i];
pos[inorder[i]]=i;
}

int root= build(0,n-1,0,n-1);
bfs(root);
return 0;
}


6天前
#include <bits/stdc++.h>
using namespace std;

int main(){
double n;
cin>>n;
double l=-10000,r=10000;
while(r-l>1e-8){
double mid=(l+r)/2;
if(mid*mid*mid>=n) r=mid;
else l=mid;
}
printf("%lf",l);
return 0;
}