5780

Pr
Snowandraw.
seeingsomeone
RyanMoriarty

@Moli

Peter_5
Linclon
Laurus_1

h111111

12小时前
#include<iostream>

using namespace std;

const int N=1010;
int a[N][N],s[N][N];

int main()
{
int n,m,q;
cin >> n >>m >> q;
for(int i=1;i<=n;i ++)
for(int j=1;j<=m;j ++)
cin >> a[i][j];
// 初始化前缀和
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]+a[i][j];
//询问
while(q--)
{
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] << endl;
}
return 0;
}


12小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

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

signed main()
{
cin >> n >> m;
for(int i=1;i<=n;i ++)
{
cin >> a[i];
s[i]=s[i-1]+a[i];
}
while(m--)
{
int l,r;
cin >> l >> r;
cout << s[r]-s[l-1] << endl;
}
return 0;
}



14小时前
#include<iostream>

using namespace std;

const int N=100010;
int w[N],h[N];//存储长、宽
int n,k;

bool chack(int mid)
{
int res=0;//记录分成长度为 mid 的巧克力数量
for(int i=0;i<n;i ++)
{
res+=((long long)h[i]/mid)*((long long)w[i]/mid);//每一大块可以分成的边长为 mid 的巧克力数量
}
if(res>=k)return true;//大于要求数量，返回真
return false;
}

int main()
{

cin >>  n >> k;
for(int i=0;i<n;i ++)
{
cin >> h[i] >> w[i];
}
int l=1,r=1e5;//小巧克力数量边长一定在 1 -- 100000 之间
while(l<r)//二分小巧克力边长范围，找到符合要求的最大值
{
int mid=(l+r+1)/2;
if(chack(mid))l=mid;
else
r=mid-1;
}
cout << r << endl;
return 0;
}



15小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=5e6+100,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

struct Sum
{
int s,c,d;
bool operator < (const Sum &t)const
{
if(s!=t.s)return s<t.s;
if(c!=t.c)return c<t.c;
if(d!=t.d)return d<t.d;
}
}sum[N];

int n,m;

signed main()
{

cin >> n;
for(int c=0;c*c<=n;c ++)
{
for(int d=c;c*c+d*d<=n;d ++)
{
sum[m++]={c*c+d*d,c,d};
}
}
sort(sum,sum+m);

for(int a=0;a*a<=n;a ++)
{
for(int b=a;b*b+a*a<=n;b ++)
{
int t=n-a*a-b*b;
int l=0,r=m-1;
while(l<r)
{
int mid=(l+r)/2;
if(sum[mid].s>=t)r=mid;
else l=mid+1;
}

if(sum[l].s==t)
{
cout << a <<' '<< b << ' ' << sum[l].c << ' ' << sum[l].d << endl;
return 0;
}
}

}

return 0;
}



17小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n;
PII  q[N];
int smax[N],smin[N];

signed main()
{
cin >> n;
for(int i=1;i<=n;i ++)
{
cin >> q[i].x >> q[i].y;
}
sort(q+1,q+1+n);

//前缀最值
smax[0]=-INF,smin[n+1]=INF;
for(int i=1;i<=n;i ++)
{
smax[i]=max(smax[i-1],q[i].y);
}
for(int i=n;i>=1;i --)
{
smin[i]=min(smin[i+1],q[i].y);
}
int res=0;
for(int i=1;i<=n;i ++)
{
if(smax[i-1]<q[i].y && smin[i+1]>q[i].y)//该点之前的最大值必须小于q[i].y，之后的最小值必须大于q[i].y
res++;
}
cout << res << endl;
return 0;
}



18小时前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

map<int,int> mp1;

signed main()
{
int n,a=0,b;
char c;
cin >>  n;
for(int i=0;i<n;i ++)
{
cin >> b >> c;
//向右走就+b
if(c=='R')
{
mp1[a]++;
mp1[a+b]--;
a+=b;
}
//向左走就 -b
else
{
mp1[a-b]++;
mp1[a]--;
a-=b;
}
}
int sum=0,ans=0,L;
for(auto [k, v] : mp1)
{
// debug3(k, v, sum);
if(sum <= 1 && sum + v > 1) L = k; //如果sum 从比2小变到比2大，那么k值就是区间左端点
else if(sum > 1 && sum + v <= 1) ans += k - L; //反之就是区间右端点
sum += v;//更新sum 的值
}
cout << ans << endl;

return 0;
}



1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;

int n;
string a[N], b[N], c[N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
b[i] = c[i] = a[i];
sort(b[i].begin(), b[i].end(), greater<char>());//b取最大，倒序
sort(c[i].begin(), c[i].end());//c取最小
}

sort(b + 1, b + n + 1);
sort(c + 1, c + n + 1);

for (int i = 1; i <= n; i ++ )
{
sort(a[i].begin(), a[i].end());
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (b[mid] >= a[i]) r = mid;
else l = mid + 1;
}

cout << r << ' ';
reverse(a[i].begin(), a[i].end());
l = 1, r = n;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (c[mid] <= a[i]) l = mid;
else r = mid - 1;
}

cout << r << endl;
}

return 0;
}



1天前

### A - Not Shading 题目

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=55,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char g[N][N];
int n,m,r,l;

void solve()
{
bool st=false;
cin >> n >> m >>r >> l;
//判断是否全是W；
for(int i=1;i<=n;i ++)
{
for(int j=1;j<=m;j ++)
{
cin >> g[i][j];
if(g[i][j]=='B')
st=true;
}
}
//如果都是W就输出-1；
if(st==false)
{
cout << -1 << endl;
return ;
}
//如果当前位置是B，就输出0；
if(g[r][l]=='B')
{
cout << 0 << endl;
return ;
}
else
{
//判断该位的行或者列有无B，如果有就输出1；
for(int i=1;i<=m;i ++)
{
if(g[r][i]=='B')
{
cout << 1 << endl;
return ;
}
}
for(int i=1;i<=n;i ++)
{
if(g[i][l]=='B')
{
cout << 1 << endl;
return ;
}
}
}
//都没有就输出2；
cout << 2 << endl;
return ;
}

signed main()
{

int T;
cin >> T;
while(T--)
{
solve();
}
return 0;
}



### B - Not Sitting 题目

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

vector<int>v;
int n,m;
void solve()
{
cin>>n>>m;
v.clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
v.push_back(max({i+j-2,i-1+m-j,n-i+j-1,n+m-i-j}));//(1,1),(1,m),(n,1),(n,m);
sort(v.begin(),v.end());
for(auto x:v)cout<<x<<' ';
cout<<endl;
}

signed main()
{

int T;
cin >> T;
while(T--)
{
solve();
}
return 0;
}



### C - Not Assigning 题目

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n;
int ans[N];
vector<PII>v[N];
int ok;
int d[N];
void dfs(int u,int fa,int q)
{
for(auto t:v[u])
{
if(t.x==fa)continue;
ans[t.y]=q;
if(q==2)dfs(t.x,u,3);
else dfs(t.x,u,2);
}
}

void solve()
{
ok=1;
cin>>n;
for(int i=1;i<=n;i++)v[i].clear(),d[i]=0;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
d[a]++,d[b]++;
if(d[a]>=3||d[b]>=3)ok=0;
v[a].push_back({b,i});
v[b].push_back({a,i});
}
for(int i=1;i<=n;i++)
{
if(d[i]==1&&ok)
{
dfs(i,-1,2);
break;
}
}
if(!ok)cout<<-1;
else
{
for(int i=1;i<n;i++)cout<<ans[i]<<' ';
}
cout<<endl;

}

signed main()
{

int T=1;
cin>>T;
while(T--)
solve();
return 0;
}


x 和 y 具有相反的奇偶性。
y 和 z 具有相反的奇偶性。
x 和 z 具有相反的奇偶性。

### D - Not Adding 题目

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=1e6+10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n,ans;
int a[N];
int f[N];

void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],f[a[i]]++;//f数组记录该数出现的次数
for(int i=N;i>=1;i--)
if(!f[i]){
int cnt=0;
for(int j=i;j<=1e6;j+=i){
if(f[j])
cnt=gcd(cnt,j);
}
if(cnt==i)ans++;
}
cout<<ans<<endl;
}

signed main()
{

int T=1;
while(T--)
solve();
return 0;
}


2天前

### A - Ancient Civilization 链接

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e5+10,M=2000010;
vector<PII>heap1,heap2;
int n,m;
int a[50];
int b[110];
int c[110][110];
void solve()
{
memset(c,0,sizeof c);
memset(a,0,sizeof a);
//n是数字个数，m是最大数字转化为2进制时的位数
cin >> n >>m;
for(int i=1;i<=n;i ++)
cin >> b[i];
int t=0;
for(int i=1;i<=n;i ++)
{
int cnt=1;
t=b[i];
while(t>0)
{
c[i][cnt]=t%2;
cnt++;
t/=2;
if(t==0)
break;
}
}

int ans=0;
//a数组记录当前这位上的答案
for(int j=1;j<=m;j ++)
{
int sum=0;//sum记录的是当前这位上1的个数
for(int i=1;i<=n;i ++)
{
sum+=c[i][j];

}
//选取多的那个数字
if(sum>n/2)
a[j]=1;
}
//将数组a转化成答案
for(int i=1;i<=m;i ++)
{
int k=i;
if(a[k]==1)
{
ans+=pow(2,k-1);
}
}
cout << ans << endl;
}

signed main()
{

int T;
cin >> T;
while(T--)
{
solve();
}
return 0;
}


### B - Elementary Particles 链接

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=150100,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n;
int a;
void solve()
{
int ans=-1;
map<int,int> q;
q.clear();
cin >> n;
for(int i=1;i<=n;i ++)
{
cin >> a;
if(q[a])
ans=max(ans,n-i+q[a]);
q[a]=i;
}
cout << ans << endl;

}

signed main()
{

int T;
cin >> T;
while(T--)
{
solve();
}
return 0;
}



### C - Road Optimization 题目

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

const int N = 500 + 5;
int dp[N][N], d[N], a[N];
const int INF =0x3f3f3f3f;

int main() {
int n, l, k;
cin >> n >> l >> k;
for (int i = 0; i < n; i++) cin >> d[i];
d[n] = l;
for (int i = 0; i < n; i++) cin >> a[i];

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = INF;
}
}
dp[0][0] = 0;

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
for (int K = 0; K < i; K++) if (j >= (i-K-1)) {
dp[i][j] = min(dp[i][j], dp[K][j-(i-K-1)] + (d[i] - d[K]) * a[K]);
}
}
}

int ans = INF;
for (int j = 0; j <= k; j++) {
ans = min(ans, dp[n][j]);
}

cout << ans << endl;
return 0;
}


for (int i = 0; i < n; i)
for (int j = 0; j <= k; j
)
{

}

2天前
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define lowbit(x) (x&-x)
#define Kido ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int INF=0x3f3f3f3f;
const int N=10,M=2000010;
vector<PII>heap1,heap2;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n;
char g[N][N];
bool st[N][N];
int ans;

void dfs(int x,int y,int cntl,int cntr)
{
st[x][y]=true;
if(cntl==cntr)
{
ans=max(ans,cntl+cntr);
st[x][y]=false;
return ;
}
for(int i=0;i<4;i ++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=0 && a<n && b>=0 && b<n && !st[a][b])
{
if(g[x][y]==')' &&g[a][b]=='(')continue;
if(g[a][b]=='(') dfs(a,b,cntl+1,cntr);
else dfs(a,b,cntl,cntr+1);
}
}
st[x][y]=false;
}
signed main()
{

cin >> n;
for(int i=0;i<n;i ++)
cin >> g[i];
if(g[0][0]=='(')
{
dfs(0,0,1,0);
}
cout << ans << endl;
return 0;
}