我怎么又是这个点写题解
这套题还是挺简单的(确信
A
#include<bits/stdc++.h>
using namespace std;
int main(){
int res;
for(int i=1; i<=5; i++){
int t; cin>>t;
if(!t) res=i;
}
cout<<res;
return 0;
}
B
#include<bits/stdc++.h>
using namespace std;
int main(){
int x, y; cin>>x>>y;
if(y&1){
puts("No");
return 0;
}
puts(y/2<=2*x && 2*x<=y? "Yes": "No");
return 0;
}
C
边界注意一下嗷。
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int buc[N];
int main(){
int x, n; cin>>x>>n;
for(int i=1; i<=n; i++){
int t; cin>>t;
buc[t]++;
}
int res=1e9, ans;
for(int i=0; i<=101; i++) if(!buc[i] && abs(i-x)<res) res=abs(i-x), ans=i;
cout<<ans;
return 0;
}
D
排序,大力去筛就行了,复杂度是 \(O(NlogN)\) ,但是要记得判重。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=2e5+5, M=5*N;
int n;
int w[N], vis[M], cnt[M];
int main(){
read(n);
rep(i,1,n) read(w[i]), cnt[w[i]]++;
sort(w+1, w+1+n);
int res=0;
rep(i,1,n){
int v=w[i];
if(vis[v]) continue;
if(!vis[v] && cnt[v]==1) res++;
for(int j=v; j<M; j+=v) vis[j]=true;
}
cout<<res;
return 0;
}
E
写了个树套树维护。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=2e5+5, cnt=2e5;
int n, q;
struct node{
int l, r;
int v;
multiset<int> val;
#define ls(u) u<<1
#define rs(u) u<<1|1
}tr[N<<2];
int pos[N], rat[N]; // msg of kid
void pushup(int u){
tr[u].v=min(tr[ls(u)].v, tr[rs(u)].v);
}
void build(int u, int l, int r){
tr[u]={l, r, INF};
if(l==r) return;
int mid=l+r>>1;
build(ls(u), l, mid), build(rs(u), mid+1, r);
pushup(u);
}
void modify(int u, int x, bool fl, int v){
if(tr[u].l==tr[u].r && tr[u].l==x){
if(fl){
auto &t=tr[u].val;
t.insert(v);
tr[u].v=*t.rbegin();
}
else{
auto &t=tr[u].val;
auto it=t.find(v);
t.erase(it);
if(t.size()) tr[u].v=*t.rbegin();
else tr[u].v=INF;
}
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(mid>=x) modify(ls(u), x, fl, v);
else modify(rs(u), x, fl, v);
pushup(u);
}
int query(int u, int l, int r){
if(tr[u].l>=l && tr[u].r<=r) return tr[u].v;
int mid=tr[u].l+tr[u].r>>1, res=INF;
if(mid>=l) res=min(res, query(ls(u), l, r));
if(mid<r) res=min(res, query(rs(u), l, r));
return res;
}
int main(){
read(n), read(q);
build(1, 1, cnt);
rep(i,1,n){
int v, p; read(v), read(p);
modify(1, p, 1, v); // insert
pos[i]=p, rat[i]=v;
}
rep(i,1,q){
int idx, p; read(idx), read(p);
int pre=pos[idx], rate=rat[idx]; // pre pos, rate
modify(1, pre, 0, rate); // delete
pos[idx]=p;
modify(1, p, 1, rate); // insert
int res=query(1, 1, cnt);
cout<<res<<endl;
}
return 0;
}
F
最短路。
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
inline void read(int &x) {
int s=0;x=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
x*=s;
}
const int N=1e6+5;
int n, m, k;
int sx, sy, tx, ty;
string g[N];
PII q[N];
int tt=-1, hh=0;
int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
int main(){
cin>>n>>m>>k>>sx>>sy>>tx>>ty;
sx--, sy--, tx--, ty--;
vector<vector<int>> d(n, vector<int>(m, INF));
vector<vector<char>> g(n, vector<char>(m));
getchar();
for(int i=0; i<n; i++, getchar()) for(int j=0; j<m; j++) g[i][j]=getchar();
d[sx][sy]=0;
q[++tt]={sx, sy};
// rep(i,0,n-1) rep(j,0,m-1) debug(g[i][j]);
while(tt>=hh){
auto hd=q[hh++];
int x=hd.first, y=hd.second;
rep(i,0,3){
rep(j,1,k){
int kx=x+dx[i]*j, ky=y+dy[i]*j;
if(kx<0 || kx>=n || ky<0 || ky>=m || d[kx][ky]<=d[x][y]) break;
if(g[kx][ky]==‘@‘) break;
if(d[kx][ky]==INF) q[++tt]={kx, ky}, d[kx][ky]=d[x][y]+1;
if(kx==tx && ky==ty) break;
}
}
}
cout<<(d[tx][ty]==INF? -1: d[tx][ty])<<endl;
return 0;
}