已做BCDEFGJ
刚开始想了个贪心，结果不对然后直接转头想dp了。 将能力值排序。 首先我们先分出来一组，能力值最大的分出来一组人数是 a n a_n an即下标是 n − a n + 1 → n n-a_n+1\to n n−an+1→n分出来一组，目前还剩 n − a n n-a_n n−an个人待分配，然后考虑设计dp 状态表示： f i f_i fi考虑前 1 1 1~ i i i个人分成的最多组数 状态转移：目前第 i i i个人可以与前面的人一组，也可以把它丢到最开始分出来的那一组于是不难得出： f i = m a x ( f i − 1 , f i − a i + 1 ) f_i=max(f_{i-1},f_{i-a_i}+1) fi=max(fi−1,fi−ai+1)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const int INF=0x3f3f3f3f; int a[N],f[N]; int n; int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); if(a[n]>n) { cout<<-1<<'\n'; continue; } n=n-a[n]; for(int i=1;i<=n;i++) { int j=max(0,i-a[i]); f[i]=max(f[i-1],f[j]+1); } cout<<f[n]+1<<'\n'; } return 0; }由于坏掉的电线杆数目很小，我们可以用bfs预处理以家和每个电线杆为起点到达其他电线杆距离的最小值。 直接枚举电线杆的顺序查表求最值即可。
全排列枚举 ( c n t ! ) (cnt!) (cnt!)会超时需要状态压缩dp枚举 ( 2 c n t ) (2^{cnt}) (2cnt)。
写本题的时候发现unordered_map的键值key不能是pair，举体原因请参考大佬博客加上一些代码就可以使用了。
#include<functional> template <typename T> inline void hash_combine(std::size_t &seed, const T &val) { seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } // auxiliary generic functions to create a hash value using a seed template <typename T> inline void hash_val(std::size_t &seed, const T &val) { hash_combine(seed, val); } template <typename T, typename... Types> inline void hash_val(std::size_t &seed, const T &val, const Types &... args) { hash_combine(seed, val); hash_val(seed, args...); } template <typename... Types> inline std::size_t hash_val(const Types &... args) { std::size_t seed = 0; hash_val(seed, args...); return seed; } struct pair_hash { template <class T1, class T2> std::size_t operator()(const std::pair<T1, T2> &p) const { return hash_val(p.first, p.second); } }; #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=210; const ll INF=1e18; int n,m,t; char g[N][N]; unordered_map<pii,int,pair_hash> mp; pii pos[20]; int dist[20][20],a[20]; bool st[N][N]; int d[N][N]; queue<pii> q; int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; ll f[1<<16][17]; void bfs(int now) { q.push(pos[now]); memset(d,0x3f,sizeof d); memset(st,0,sizeof st); d[pos[now].first][pos[now].second]=0; while(q.size()) { int x=q.front().first,y=q.front().second;q.pop(); if(st[x][y]) continue; st[x][y]=1; if(g[x][y]!='.') dist[now][mp[{x,y}]]=d[x][y]; for(int i=0;i<4;i++) { int a=x+dx[i],b=y+dy[i]; if(a<1||b<1||a>n||b>m||g[a][b]=='#') continue; if(d[a][b]>d[x][y]+1) { d[a][b]=d[x][y]+1; q.push({a,b}); } } } } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n>>m>>t; for(int i=1;i<=n;i++) cin>>g[i]+1; int cnt=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(g[i][j]=='S') mp[{i,j}]=0,pos[0]={i,j}; else if(g[i][j]=='T') mp[{i,j}]=++cnt,pos[cnt]={i,j}; } memset(dist,0x3f,sizeof dist); for(int i=0;i<=cnt;i++) bfs(i); memset(f,0x3f,sizeof f); f[1][0]=0; for(int i=0;i<1<<cnt+1;i++) for(int j=0;j<=cnt;j++) if(i>>j&1) for(int k=0;k<=cnt;k++) if((i-(1<<j))>>k&1) f[i][j]=min(f[i][j],f[i-(1<<j)][k]+dist[k][j]); ll res=INF; for(int i=1;i<=cnt;i++) res=min(res,f[(1<<cnt+1)-1][i]+dist[i][0]); if(res>=0x3f3f3f3f) cout<<-1<<'\n'; else { res+=1ll*t*cnt; cout<<res<<'\n'; } } return 0; }数据保证，任何时候这n个数字均互不相同。 这个条件非常重要，有了这个条件直接用线段树维护一下区间最大值和最小值即可：如果最大值和最小值的差等于坐标差就满足题意否则不满足。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const int INF=0x3f3f3f3f; int a[N]; int n,q; struct node { int l,r; int mx,mn; }tree[N*4]; void pushup(int u) { tree[u].mx=max(tree[u<<1|1].mx,tree[u<<1].mx); tree[u].mn=min(tree[u<<1|1].mn,tree[u<<1].mn); } void build(int u,int l,int r) { tree[u]={l,r,-INF,INF}; if(l==r) { tree[u].mn=tree[u].mx=a[l]; return; } int mid=l+r>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } void modify(int u,int pos,int val) { if(tree[u].l==tree[u].r) { tree[u].mn=tree[u].mx=val; return; } int mid=tree[u].l+tree[u].r>>1; if(pos<=mid) modify(u<<1,pos,val); else modify(u<<1|1,pos,val); pushup(u); } int querymx(int u,int l,int r) { if(tree[u].l>=l&&tree[u].r<=r) return tree[u].mx; int mid=tree[u].r+tree[u].l>>1; int v=-INF; if(l<=mid) v=max(v,querymx(u<<1,l,r)); if(r>mid) v=max(v,querymx(u<<1|1,l,r)); return v; } int querymn(int u,int l,int r) { if(tree[u].l>=l&&tree[u].r<=r) return tree[u].mn; int mid=tree[u].r+tree[u].l>>1; int v=INF; if(l<=mid) v=min(v,querymn(u<<1,l,r)); if(r>mid) v=min(v,querymn(u<<1|1,l,r)); return v; } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); while(q--) { int op,x,y; cin>>op>>x>>y; if(op==1) modify(1,x,y); else { if(y-x==querymx(1,x,y)-querymn(1,x,y)) cout<<"YES\n"; else cout<<"NO\n"; } } } return 0; }正解是bitset+拓扑排序，由于数据范围很小随便搞都能过 我还是补一补正解吧，正好练习一下bitset使用。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=2010; int h[N],e[N],ne[N],idx; int d[N]; bitset<1005>b[N]; int n,m; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } void topsort() { queue<int> q; for(int i=1;i<=n;i++) if(!d[i]) q.push(i); while(q.size()) { int t=q.front();q.pop(); for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; b[j]|=b[t]; b[j][t]=1; if(--d[j]==0) q.push(j); } } } int main() { IO; int T=1; //cin>>T; while(T--) { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int a,b; cin>>a>>b; add(a,b); d[b]++; } topsort(); for(int i=1;i<=n;i++) cout<<b[i].count()<<'\n'; } return 0; }剩下的题待做。
要加油哦~
