简单点评一下
整体上来看 ，A题拿满分的同学可能占一半吧 ，这个数据其实是不太理想的 ，说明同学们对于思维模拟题还是不熟练，没抓住题目要分析的本质。
B题显然是保证有解的，有解的情况下问最优解，说明翻到满足要求的方案不止一种，我们要找最优解，数据一看很小，应该很容易联想到dfs，把所有方案搜索到然后取min即可 ，可以从第一行开始处理，每个位置攻击还是不攻击，一共有2m 种选择 ，然后剩下的位置可以依据上一行的摆放来计算出是否要攻击，所以说整体时间复杂度 O ( 2 O(2 O(2m * n2 )
C题不会写正解为什么不会写暴力呢？？？ 什么叫暴力？
不考虑时间不考虑空间直接按题目意思去模拟，当然最好还是按自己能力做一些优化 ，
这都是得分技巧
D题全场0分
这两套题打完基本上可以观察出同学们水平还未达到普及+
训练应该侧重思维，模拟，以及对算法的掌握上。
未来不会再放这种难度的套题了 …
#include <bits/stdc++.h>
using namespace std;
int T,num,ans;
string s;
int main()
{T = 1;while (T--){cin>>s;num = ans = 0;for (auto &ch : s){if (ch == 'A') num++;if (ch == 'P'){if (num > 0) num--; else ans++;}}ans = ans % 2 + num;cout<<ans<<endl;}return 0;
}
#include <bits/stdc++.h>
using namespace std;
char st[29][29];
int n,m,ans,sum;
int a[29],b[29][29],map1[29][29];
void ds(int x,int y)
{b[x][y]=!b[x][y];b[x-1][y]=!b[x-1][y];b[x+1][y]=!b[x+1][y];b[x][y-1]=!b[x][y-1];b[x][y+1]=!b[x][y+1];sum++;
}
void dfs(int dep)
{int f;if(dep>m){sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]=map1[i][j];for(int i=1;i<=m;i++)if(a[i]==1) ds(1,i);for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(b[i-1][j]==1) ds(i,j);f=1;for(int i=1;i<=m;i++)if(b[n][i]==1) f=0; if(f&&sum<ans) ans=sum;return ;}a[dep]=0;dfs(dep+1);a[dep]=1;dfs(dep+1);
}
int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>st[i][j];if(st[i][j]=='X') map1[i][j]=1;elsemap1[i][j]=0; }ans=n*m;dfs(1);printf("%d",ans);return 0;}
当然这题暴力可以拿70分。。。。但是很多同学不去写
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize(3, "Ofast", "inline")
#define fir(i, a, b) for (int i = a; i <= b; i++)const int maxn=1e7+10;
const int MAX_INF=0x3f3f3f3f;
int a[maxn];
int k,n;
struct node
{int l;int r;int val;
};
#define left (i<<1)
#define right (i<<1|1)
node seg[maxn*4];
void change_node(int i,int val){seg[i].val+=val;
}
void push_down(int i){if(seg[i].val){change_node(left,seg[i].val);change_node(right,seg[i].val);seg[i].val=0;}
}
void build(int l,int r,int i)
{seg[i].l=l;seg[i].r=r;if(l==r){seg[i].val=a[l];return;}int mid=(l+r)>>1;build(l,mid,left);build(mid+1,r,right);
}
void change(int l,int r,int i,int val){if(l<=seg[i].l&&seg[i].r<=r){change_node(i,val);return;}push_down(i);int mid=(seg[i].l+seg[i].r)>>1;if(l<=mid)change(l,r,left,val);if(r>mid)change(l,r,right,val);
}
int query(int x,int i){if(seg[i].l==seg[i].r&&seg[i].l==x)return seg[i].val;push_down(i);int mid=(seg[i].l+seg[i].r)>>1;if(x<=mid)return query(x,left);return query(x,right);
}
void work()
{int l=1,r=n+1;while(l<r){int mid=(l+r+1)>>1;if(query(mid,1)>mid)r=mid-1;else l=mid;}if(query(l,1)==l)puts("YES");else puts("NO");
}
int main()
{ scanf("%d%d",&k,&n);fir(i,1,n)scanf("%d",&a[i]);a[n+1]=MAX_INF;build(1,n+1,1);work();k--;while(k--){int l,r,c;
// cin>>l>>r>>c;scanf("%d%d%d",&l,&r,&c);change(l,r,1,c);work();}
}
#include <bits/stdc++.h>using namespace std;#define all(x) (x).begin(), (x).end()
#define fi first
#define se secondtypedef vector<int> VI;
typedef long long ll;
typedef pair<ll,int> pii;
// head
/**
7 11
1 2
2 3
2 4
3 4
3 7
4 5
4 6
4 7
5 6
5 7
6 7
*/const int N = 10e5+5;
const int M = N * 2;
ll NN,MM,BB;struct DSU {int fa[N];int *core_;int find(int x) {return (x == fa[x]) ? x : (fa[x] = find(fa[x]));}void init(int n, int *core_) {this->core_ = core_;for (int i = 0; i <= n; i++)fa[i] = i;}void joint(int u, int v) {u = find(u), v = find(v);if (u != v) {if ((core_[u] > core_[v]) || (core_[u] == core_[v] && u > v)) {swap(v, u);}fa[v] = u;}}
} dsu;struct Graph {struct Edge {int to, nxt;Edge(int to, int nxt) : to(to), nxt(nxt) {}Edge() {}};int head[N], ec, n, max_deg;Edge e[M];void addEdge(int from, int to) {e[ec] = Edge(to, head[from]);head[from] = ec++;core_[to]++;}void init(int n) {ec = 0;this->n = n;for (int i = 0; i <= n; i++)head[i] = -1, core_[i] = 0;}int seq_[N], core_[N], bin_[N], kmax;void generate_core() {VI pos_(n, 0);memset(bin_, 0, sizeof(int) * n);max_deg = 0;for (int v = 0; v < n; ++v) {bin_[core_[v]]++;max_deg = max(max_deg, core_[v]);}int start = 0;for (int d = 0; d <= max_deg; ++d) {int num = bin_[d];bin_[d] = start;start += num;}for (int v = 0; v < n; ++v) { //O(V) create p and Dpos_[v] = bin_[core_[v]];seq_[pos_[v]] = v;bin_[core_[v]]++;}for (int d = max_deg; d >= 1; --d) {bin_[d] = bin_[d - 1];}bin_[0] = 0;bin_[max_deg + 1] = n;for (int i = 0; i < n; ++i) { //O(E) delete all Nodes from D[]int v = seq_[i];for (int j = head[v]; ~j; j = e[j].nxt) {int u = e[j].to;if (core_[u] > core_[v]) {int du = core_[u], pu = pos_[u];int pw = bin_[du], w = seq_[pw];if (u != w) {pos_[u] = pw;seq_[pu] = w;pos_[w] = pu;seq_[pw] = u;}bin_[du]++;core_[u]--;}}}kmax = *std::max_element(core_, core_ + n);}VI get_kshell(int k) {return VI(seq_ + bin_[k], seq_ + bin_[k + 1]);}int tid_[N];int tn;VI pa, tk;void build_tree() {tn = 0;memset(tid_, -1, sizeof(int) * n);dsu.init(n, core_);pa.clear();tk.clear();for (int k = kmax; k >= 0; k--) {VI k_shell = get_kshell(k);set<int> kpc_pivot;for (auto v : k_shell) {for (int j = head[v]; ~j; j = e[j].nxt) {int nbr = e[j].to;int pivot = dsu.find(nbr);if (core_[pivot] > k) {kpc_pivot.insert(pivot);}if (core_[pivot] >= k) {dsu.joint(v, pivot);}}}for (auto v : k_shell) {int pivot = dsu.find(v);if (tid_[pivot] == -1) {tid_[pivot] = tn++;pa.push_back(-1);tk.push_back(core_[pivot]);}int cur_tid = tid_[pivot];tid_[v] = cur_tid;}for (auto v : kpc_pivot) {int pivot = dsu.find(v);int tid_ch = tid_[v], tid_pa = tid_[pivot];pa[tid_ch] = tid_pa;}}}void compute() {VI vert(tn, 0), edge(tn, 0), boun(tn, 0);for (int i = 0; i < n; i++) {int ci = core_[i];int lt = 0, eq = 0, gt = 0;for (int j = head[i]; ~j; j = e[j].nxt) {int nbr = e[j].to;int cnbr = core_[nbr];if (cnbr < ci) lt++;else if (cnbr == ci) { if (i < nbr) eq++; }else gt++;}int ti = tid_[i];vert[ti]++;edge[ti] += gt + eq;boun[ti] += lt - gt;}pii ans(1LL*(-1e18), -1);for (int i = 0; i < tn; i++) {int f = pa[i];if (f != -1) {vert[f] += vert[i];edge[f] += edge[i];boun[f] += boun[i];}ll score = MM*edge[i] - NN*vert[i] + BB*boun[i];if (tk[i]>0)ans = max(ans, {score, tk[i]});}printf("%d %lld\n", ans.second, ans.first);}
} g;
int main() {int n, m, u, v;while (scanf("%d%d", &n, &m) == 2) {scanf("%lld%lld%lld",&MM,&NN,&BB);g.init(n);for (int i = 0; i < m; i++) {scanf("%d%d", &u, &v);u--, v--;g.addEdge(u, v);g.addEdge(v, u);}g.generate_core();g.build_tree();g.compute();}return 0;
}
