题目链接 http://codeforces.com/contest/1065
A. Vasya and Chocolate
题意: 已知钱, 价格, 赠送规则求最多获得巧克力数
思路: 常规算即可
- #include <bits/stdc++.h>
- #define DBG(x) cerr <<#x << "=" << x << endl;
- using namespace std;
- typedef long long LL;
- LL t,s,a,b,c;
- int main(){
- cin>> t;
- while(t--){
- cin>> s>> a>> b>> c;
- LL ans=s/c;
- ans+=(ans/a)*b;
- cout <<ans << endl;
- }
- return 0;
- }
- B. Vasya and Isolated Vertices
题意: 给出无向图点和边数问最多和最少孤立点的数量
思路: 使孤立点尽可能少就让一条边尽可能消去两个点, 否则让其尽可能消去一个点
- #include <bits/stdc++.h>
- #define DBG(x) cerr <<#x << "=" << x << endl;
- using namespace std;
- typedef long long LL;
- LL n,m,i;
- int main(){
- scanf("%I64d%I64d",&n,&m);
- while(i*(i-1)/2 < m)i++;
- printf("%I64d %I64d\n",(m*2 < n) ? n-m*2 : 0,n-i);
- return 0;
- }
- C. Make It Equal
题意: 给出一些块柱, 每次移动一层及以上所有块, 在一次不移动超过 k 的前提下使所有柱高度一致的最少次数
思路: 枚举当前移动的高度, 使被移动的块尽可能接近 k, 需要预处理每层会影响的块数, 枚举高度二分找位置, 维护后缀即可完成预处理
- #include <bits/stdc++.h>
- #define DBG(x) cerr <<#x << "=" << x << endl;
- const int inf = 0x3f3f3f3f;
- const int maxn = 2e5+5;
- using namespace std;
- int n,k,a[maxn],maxH=-inf;
- int b[maxn];
- vector<int>vec;
- int main(){
- scanf("%d%d",&n,&k);
- for(int i=1;i<=n;i++)scanf("%d",&a[i]);
- sort(a+1,a+1+n);
- for(int i=2;i<=n;i++){
- int det=a[i]-a[1];
- maxH=max(maxH,det);
- if(det)vec.push_back(det);
- }
- int siz=vec.size();
- for(int i=maxH;i>=1;i--){
- b[i]=lower_bound(vec.begin(),vec.end(),i)-vec.begin()+1;
- b[i]=siz-b[i]+1;
- b[i]+=b[i+1];
- }
- int now=0,cnt=0;
- for(int i=maxH;i>=1;i--){
- if(b[i]-now> k)now=b[i+1],cnt++;
- }
- if(now != b[1] && b[1]-now <= k)cnt++;
- printf("%d\n",cnt);
- return 0;
- }
- D. Three Pieces
题意: 给定棋盘和三颗棋子, 问遍历棋盘的最少步数即满足最少步数前提下替换棋子的最少次数
思路: 从起点开始大力搜索, 枚举所有可能的后继状态
- #include <bits/stdc++.h>
- #define DBG(x) cerr <<#x << "=" << x << endl;
- const int maxn = 15;
- const int maxm = 205;
- const int inf = 0x3f3f3f3f;
- using namespace std;
- int n,k;
- int mp[maxn][maxn],vis[maxn][maxn],dp[maxn][maxn][3][maxm][maxm];
- int sx,sy,ex,ey;
- int dx1[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
- int dx2[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
- int dx3[4][2]={{-1,-1},{-1,1},{1,-1},{1,1}};
- int ans=inf;
- struct node{
- int r,c,who,time,pre;
- node(int _r,int _c,int _who,int _time,int _pre){
- r=_r,c=_c,who=_who,time=_time,pre=_pre;
- }
- };
- void bfs(int sx, int sy) {
- memset(dp, -1, sizeof dp);
- dp[sx][sy][0][0][1] = dp[sx][sy][1][0][1] = dp[sx][sy][2][0][1] = 0;
- queue<node>q;
- q.push(node(sx, sy, 0, 0, 1));
- q.push(node(sx, sy, 1, 0, 1));
- q.push(node(sx, sy, 2, 0, 1));
- while(!q.empty()) {
- node nd = q.front();
- q.pop();
- int x = nd.r, y = nd.c, z = nd.who, t = nd.time, k = nd.pre;
- for(int i = 0; i <3; i++) {
- if(i == z) continue;
- if(dp[x][y][i][t + 1][k] != -1) continue;
- dp[x][y][i][t + 1][k] = dp[x][y][z][t][k] + 1;
- q.push(node(x, y, i, t + 1, k));
- }
- if(z == 0) {
- for(int i = 0; i < 8; i++) {
- int nx=x+dx1[i][0];
- int ny=y+dx1[i][1];
- int nk=k;
- if(nx < 1 || nx> n || ny <1 || ny> n) continue;
- if(mp[nx][ny] == k + 1) nk++;
- if(dp[nx][ny][z][t][nk] != -1) continue;
- dp[nx][ny][z][t][nk] = dp[x][y][z][t][k] + 1;
- q.push(node(nx, ny, z, t, nk));
- }
- }
- if(z == 1) {
- for(int i = 0; i <4; i++) {
- for(int j = 1;j <= 10;j++) {
- int nx=x+j*dx2[i][0];
- int ny=y+j*dx2[i][1];
- int nk=k;
- if(nx < 1 || nx> n || ny <1 || ny> n) continue;
- if(mp[nx][ny] == k + 1) nk++;
- if(dp[nx][ny][z][t][nk] != -1) continue;
- dp[nx][ny][z][t][nk] = dp[x][y][z][t][k] + 1;
- q.push(node(nx, ny, z, t, nk));
- }
- }
- }
- if(z == 2) {
- for(int i = 0; i <4; i++) {
- for(int j = 1;j <= 10;j++) {
- int nx=x+j*dx3[i][0];
- int ny=y+j*dx3[i][1];
- int nk=k;
- if(nx < 1 || nx> n || ny <1 || ny> n) continue;
- if(mp[nx][ny] == k + 1) nk++;
- if(dp[nx][ny][z][t][nk] != -1) continue;
- dp[nx][ny][z][t][nk] = dp[x][y][z][t][k] + 1;
- q.push(node(nx, ny, z, t, nk));
- }
- }
- }
- }
- }
- int main(){///0 == knight,1 == bishop,2 == rook
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- scanf("%d",&mp[i][j]);
- if(mp[i][j] == 1){sx=i;sy=j;}
- if(mp[i][j] == n*n){ex=i;ey=j;}
- }
- }
- bfs(sx,sy);
- for(int i=0;i<maxm;i++){
- for(int j=0;j<3;j++){
- if(dp[ex][ey][j][i][n*n] != -1)ans=min(ans,dp[ex][ey][j][i][n*n]);
- }
- }
- for(int i=0;i<maxm;i++){
- for(int j=0;j<3;j++){
- if(dp[ex][ey][j][i][n*n] == ans){printf("%d %d\n",ans,i);return 0;}
- }
- }
- }
- E. Side Transmutations
看这篇 https://www.cnblogs.com/DuskOB/p/10034474.html
F. Up and Down the Tree
看这篇 https://www.cnblogs.com/DuskOB/p/10034536.html
来源: http://www.bubuko.com/infodetail-2864946.html