首页 > 代码库 > Codeforces Round #374 (Div. 2)解题报告
Codeforces Round #374 (Div. 2)解题报告
Problem B: Passwords
题意：给出n个字符串密码，在给出一个正确密码，输密码必须先输入简单的密码，连续输错k次密码会罚时5秒，输一次密码耗时1秒，求可能的最短和最长的耗时。（注意：给出的n个密码可能包含多个正确密码）
思路：略
code：
#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#include <iostream>#include <algorithm>#define rep(i,k,n) for(int i = k;i < n;i ++)#define repp(i,k,n) for(int i = k;i <= n;i ++)#define scan(d) scanf("%d",&d)#define scanl(d) scanf("%I64d",&d)#define scann(n,m) scanf("%d %d",&n,&m)#define scannl(n,m) scanf("%I64d %I64d",&n,&m)#define mst(a,k) memset(a,k,sizeof(a))#define mod 1e9+7#define ll long long#define maxn 105using namespace std;int cnt[maxn];map<string,int> mmap;string p,s;int main(void){ int n,k; cin >> n >>k; mst(cnt,0); mmap.clear(); for(int i = 1;i <= n;i ++){ cin >> p; mmap[p] ++; cnt[p.size()] ++; } cin >> s; int len = s.size(); int cnt1,cnt2; cnt1 = cnt2 = 0; for(int i = 1;i <= len - 1;i ++){ cnt1 += cnt[i]; } cnt2 += cnt[len]; cnt2 -= (mmap[s]); int ans1,ans2; ans1 = (cnt1/k)*5 + 1 + cnt1; ans2 = ((cnt1 + cnt2)/k)*5 + cnt1 + cnt2 + 1; printf("%d %d\n",ans1,ans2); return 0;}
Problem C: Journey
题意：给出一个有n个节点的有向图，每条路包含一个权值表示走过这条路的时间，要求在给出的总时间T内必须从起点1走到终点n，求在满足条件的情况下，走过节点数的最大值。
思路：dfs + dp。dp[i][t]表示走到第i个节点路过节点数为t时使用的最小时间的，则dp[i][t] = min(dp[k][t-1]+t[k][i],dp[i][t])。
code:
#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#include <iostream>#include <algorithm>#define rep(i,k,n) for(int i = k;i < n;i ++)#define repp(i,k,n) for(int i = k;i <= n;i ++)#define scan(d) scanf("%d",&d)#define scanl(d) scanf("%I64d",&d)#define scann(n,m) scanf("%d %d",&n,&m)#define scannl(n,m) scanf("%I64d %I64d",&n,&m)#define mst(a,k) memset(a,k,sizeof(a))#define mod 1e9+7#define inf 2000000005#define ll long long#define maxn 5005using namespace std;int edgesCnt;int head[maxn];int fa[maxn][maxn]; //fa[i][j]表示走到第i个节点时走过了j个节点时的前驱int dp[maxn][maxn]; //dp[i][t]表示走到第i个节点路过节点数为t时使用的最小时间的，则dp[i][t] = min(dp[k][t-1]+t[k][i],dp[i][t])。int n,m,Tot;struct Edge{ int to; int dist; int next;}edges[maxn];void init(){ edgesCnt = 0; memset(head,-1,sizeof(head));}void addEdge(int from,int to,int d){ edges[edgesCnt].dist = d; edges[edgesCnt].to = to; edges[edgesCnt].next = head[from]; head[from] = edgesCnt; edgesCnt ++;}void dfs(int u,int step){ for(int j = head[u];j != -1;j = edges[j].next){ int v = edges[j].to; int d = edges[j].dist; if(dp[v][step+1] > dp[u][step]+d && dp[u][step]+d <= Tot){ dp[v][step+1] = dp[u][step]+d; fa[v][step+1] = u; dfs(v,step+1); } }}//递归输出路径void print(int u,int j){ if(u == 1) { printf("1 "); return; } else{ print(fa[u][j],j-1); } printf("%d ",u); if(u == n) printf("\n");}int main(void){ cin >> n >> m >> Tot; init(); for(int i = 1;i <= m;i ++){ int u,v,d; scanf("%d %d %d",&u,&v,&d); addEdge(u,v,d); } for(int i = 1;i <= n+1;i ++){ for(int j = 1;j <= n+1;j ++){ dp[i][j] = inf; } } dp[1][1] = 0; dfs(1,1); for(int i = n;i >= 1;i --){ if(dp[n][i] <= Tot){ printf("%d\n",i); print(n,i); return 0; } } return 0;}
Problem D: Maxim and Array
题意：给出一个包含n个数的数组，给出一个整数x，执行k次操作（对数组任意一个元素加x或减x）。求数组的积最小。
思路：若数组的积的符号是负，则每次操作只需要对绝对值最小的元素执行操作；若数组的积是正，则同样是最绝对值最小的元素进行操作，目的是尽快实现变号，若无法变号，也可以使积变小。综上，只需使用优先队列处理至多k次操作即可。
code:
#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#include <iostream>#include <algorithm>#define rep(i,k,n) for(int i = k;i < n;i ++)#define repp(i,k,n) for(int i = k;i <= n;i ++)#define scan(d) scanf("%d",&d)#define scanl(d) scanf("%I64d",&d)#define scann(n,m) scanf("%d %d",&n,&m)#define scannl(n,m) scanf("%I64d %I64d",&n,&m)#define mst(a,k) memset(a,k,sizeof(a))#define mod 1e9+7#define ll long long#define maxn 200005using namespace std;ll a[maxn];ll n,k,x;int flag;struct node{ int id; ll value; bool flag; //状态，1代表正，0代表负 bool operator < (const node& rhs) const{ return value > rhs.value; }};int main(void){ while(cin >> n >> k >> x){ priority_queue<node> Q; //Q.clear(); while(!Q.empty()) Q.pop(); int cnt = 0; for(int i = 1;i <= n;i ++) { cin >> a[i]; node p; if(a[i] < 0) { cnt ++; p.value = abs(a[i]); p.flag = 0; p.id = i; Q.push(p); } else{ p.value = abs(a[i]); p.flag = 1; p.id = i; Q.push(p); } } flag = cnt%2?-1:1; ll sum = x*k; while(k){ node tp = Q.top(); Q.pop(); ll id,value,f; id = tp.id; value = tp.value; f = tp.flag; if(flag == 1){ //符号为正 if(sum > value){ a[id] -= f == 1?(value/x)*x:(-value/x)*x; k -= (value/x); sum = k*x; if(a[id] >= 0 && f == 1) {a[id] -= x; k --; sum -= x;} if(a[id] < 0 && f == 0) {a[id] += x; k --; sum -= x;} flag = -1; node p; p.flag = f == 1?0:1; p.id = id; p.value = abs(a[id]); Q.push(p); } else{ a[id] -= f == 1?sum:-sum; k = sum = 0; } } else{ //符号为负 a[id] += f == 1?x:-x; k --; sum -= x; node p; p.flag = f == 1?1:0; p.id = id; p.value = abs(a[id]); Q.push(p); } } for(int i = 1;i <= n;i ++) printf("%I64d ",a[i]); cout << endl; } return 0;}
Codeforces Round #374 (Div. 2)解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。