如果您想了解mysql基础一，续2018-10-23的相关知识，那么本文是一篇不可错过的文章，我们将对mysql基础教程进行全面详尽的解释，并且为您提供关于1，Django基础一、2018ChinaC
如果您想了解mysql 基础一，续 2018-10-23的相关知识，那么本文是一篇不可错过的文章，我们将对mysql基础教程进行全面详尽的解释，并且为您提供关于1，Django 基础一、2018 China Collegiate Programming Contest Final (CCPC-Final 2018)(A B G I L)、2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) Solution、2018-2019赛季多校联合新生训练赛第三场(2018/12/8)补题题解的有价值的信息。
本文目录一览：- mysql 基础一，续 2018-10-23（mysql基础教程）
- 1，Django 基础一
- 2018 China Collegiate Programming Contest Final (CCPC-Final 2018)(A B G I L)
- 2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) Solution
- 2018-2019赛季多校联合新生训练赛第三场(2018/12/8)补题题解
mysql 基础一，续 2018-10-23（mysql基础教程）
mysql授权权限部分：
1,grant 权限 on 数据库.数据表 to ''用户'' @ ''主机名'';
grant all on *.* to ''xiaogang''@''%'';
这个时候 xiaogang 就拥有了 所有权限了
2.在mysql中给普通用户授权：
在数据库所在的服务端给普通用户设置权限
命令： grant all on *.* to ''yunjisuan''@''192.168.200.142'' identified by ''123123'';
上面表示：本地yunjisuan用户，只能登录192.169.200.142这个本地ip
在本地，以yunjisuan普通用户，以远程登录本地数据库，步骤如下-----
mysql -uyunjisuan -p123123 -h 192.168.200.142
刷新一下--------------
flush privileges;
在本地yunjisuan普通用户以本地方式登录本地数据库，步骤如下-----
授权,yunjisuan用户，以本地方式连接数据库；
grant all on *.* to ''yunjisuan''@''127.0.0.1'' identified by ''123123'';
flush privileges; 刷新一下
查看下授权信息：select user,host from mysql.user;
以本地方式登录本地数据库:
不通主机数据库的连接：
A主机ip：192.168.200.152
B主机ip：192.168.200.142
若A连通B主机的数据库，步骤如下------：
（1）在B数据库中给A授权：
grant all on *.* to ''yunjisuan''@''192.168.200.154'' identified by ''123123'';
flush privileges;刷新
（1）切换到A主机。开始登录B主机 数据库：
mysql -uyunjisuan -p123123 -h 192.168.200.142
（3）然后在A端。便可以远程操作B端 数据库
3.查权限：
show grandson；
Show grands fot ‘bennet’@’192.168.200.113’
select user(); 查看当前用户
mysql 数据库中给用户修改密码：
update mysql.user set password=password(111111) where user=''yunjisuan'';
记得刷新哈 ： flush privileges;
最后：便可以，以新密码，以本地，本地方式登录数据库，本地远程登录
或者
从其他主机上，登录数据库主机，本地方式登录数据库，本地远程登录
1，Django 基础一
Django 基础
基础知识：
1，什么是web应用？
web本质就是一个socket服务端，用户的浏览器就是一个socket客户端，基于c/s架构的b/s软件开发架构的应用
浏览器中敲入网址回车发送了几件事?
1.浏览器超服务端发送请求
2.服务端接收请求
3.服务端返回相应的响应
4.浏览器接收响应 根据特定的规则渲染页面展示给用户看
2，HTTP协议主要规定了客户端和服务端之间的通信格式
3，什么是HTTP协议：
超文本传输协议：规定了客户端与服务端消息传输的格式
http的四大特性：
1，基于请求响应
2，基于TCP/IP之上的作用于应用层的协议
3，无状态（服务端无法保存用户的输入状态，一个人来一千次都记不住，都如初见）
4，无连接（请求来一次响应一次，之后立马断开，之后两者再无任何关系，）
websocket 相当于是HTTP协议的一个大的补丁 它支持长连接
请求格式：
请求首行： http版本信息，以及客户请求方式，和url
请求头：一大堆的k,v 键值对信息（注意下面的空行不能少）
请求体：post请求携带的数据
响应数据格式：
响应首行（标识http协议版本，响应状态码）
响应头（一大堆k,v 键值对）
响应体（返回给浏览器页面的数据 通常响应体都是HTML页面
响应状态码：
用一串简单的数字来表示一些复杂的状态或者提示信息
1XX: 服务器已经成功接受到你的数据正在处理，还可以发送额外数据
2XX: 请求成功 服务器已经将你请求的数据发送给你了
3XX: 重定向
4XX: 请求错误或者没有操作权限，或内容不存在
5XX: 服务器内部错误
请求的方式：
1，get请求，向服务端获取数据，
2，port请求，超服务端提交数据
URL ：统一资源定位符（大白话就是网址）
一：Web 框架
python 三大主流web框架
1.Django:
优点：大而全 自带的功能特别特别多，类似于航空母舰
缺点：有点笨重
2.Flask：
优点：短小精悍，自带的功能模块特别少 全都是依赖第三方组件
flask框架第三方的组件特别多 如果把flask全部的组件加起来
完全可以覆盖过整个Django
确定：比较受限于第三方的开发者
3.Tornado：
优点：天生的异步非租塞框架 速度特别快 能够抗住高并发 可以开发游戏 服务器
web 框架可以分为三个部分：
A: socket
B: 路由与视图函数匹配
C: 模板语法
Django：
A用的别人的 wsgiref（模块文件）
b自己写的
c自己写的
Flask：
a用的别人的 werkzeug
b自己写的
c用别人写的 jinja2
Tornado:
a,b,c都是自己写的
ps：在介绍Django之前的注意事项，即使用Django注意事项
1.计算机的名称不能有中文
2.一个pycharm窗口就是一个项目，不要多个项目放在一个窗口里面
3.项目名不能起中文
Web流程图：
Django的版本：推荐使用1.11.11（是可以维护的）
18年之后才有2.0的版本，LTS 表示可维护的版本
下载：
命令行直接下载
pip3 install django 此时默认为最新版本
pip3 install Django==1.11.11
查看是否下载成功：
django-admin
成功后创建项目：
创建django项目的方式
方式1(命令行创建)：
1，创建django项目
django-admin startproject 项目名
django-admin startproject mysite
项目就相当于大学下面的学院，在这里只是个空壳，
所以要在项目下创建自己的应用（app）即自己学院的学科，每个应用不同，其功能就不同
2，创建应用（app）：（要切换到项目文件夹下）
切换到项目文件夹下用：cd 项目名。 例如：cd mysite
第一中方法：
django-admin startapp 应用名
django-admin startapp app01
第二中方法：
python manage.py startapp app01
3 命令行启动django 项目
python manage.py runserver
启动成功命令行会有一行（Starting development server at http://127.0.0.1:8000/）
ps：启动成功后，在起了一个django窗口后，再不要去起另一个，在端口没改的情况下别起另外的端口
如果要起窗口，必须把当前启动的窗口停了，关了，再去起窗口，停用ctrl+z键停掉，腾出端口号 退出
pycharm创建
方式2(pycharm创建)
FILE >>> new project 选择第二个django 需要注意名字不能有中文，选择本地的解释器，勾选后台管理
创建app
pycharm命令行创建
python3 manage.py startapp app01
Tools下面run manage task功能栏
启动点小绿色箭头
（**********************************）
注意：1，用命令行创建的django项目，不会自动创建templates模板文件夹
需要我们手动创建 并且需要自己去settings.py文件中注册该文件路径
2，创建的应用一定要在settings.py文件中进行注册，才能生效，否则无法识别
d
jango主要文件介绍
项目文件名：同名的项目文件夹：
settings.py 文件 django 暴露给用户的可配置文件
urls.py 文件 路由与视图函数对应的文件
wsgi.py 文件 是模块wsgiref的文件
manage.py文件 django 的入口文件应用文件（app）：
migrations文件夹 数据库迁移记录文件
admin.py 文件 django后台管理
apps.py文件 应用注册相关
models.py 文件 orm模型类
tests.py 测试文件
views.py 视图函数文件
小白必会三板斧：######################
1， HttpResponse：返回字符串，你在里面写字符串，返回字符串相关的
HttpResponse(''你好啊，我是你的第一个Django'')
2，返回页面：
所有的页面html相关的都在templates里面写，在这个文件夹下创建HTML文件
render: 返回html页面 并且能够给该页面传值
3，redirect：重定向
强调:
1.用django一定要保证只有一个在运行状态 切记切记！！！！！！！
2.一定记得清浏览器的缓存
2018 China Collegiate Programming Contest Final (CCPC-Final 2018)(A B G I L)
A: 签到题，正常模拟即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1e5 + 5;
4 struct node{
5 int id, time;
6 };
7 node a[maxn];
8 bool cmp(const node &a, const node &b){
9 if(a.id^b.id) return a.id < b.id;
10 else return a.time < b.time;
11 }
12 int main()
13 {
14 std::ios::sync_with_stdio(false);
15 int n, m, t;
16 cin >> t;
17 for(int cas = 1;cas <= t;cas++)
18 {
19 cin >> n >> m;
20 for(int i = 0;i < n;i++) cin >> a[i].id;
21 for(int i = 0;i < n;i++) cin >> a[i].time;
22 int ans = 0;sort(a, a + n, cmp);
23 int sum = 0;
24 for(int i = 0;i < n;i++)
25 {
26 if(sum + a[i].time <= m) sum += a[i].time, ans ++;
27 else break;
28 }
29 cout << "Case " << cas << ": ";
30 cout<< ans << endl;
31 }
32 return 0;
33 }B: 对于差值尽量小的问题，可以采用枚举最小值，然后使得最大值尽量小。
首先二分图判定，然后分块，求出每块的光明状态的最大最小值，黑暗状态的最大最小值，然后按分块编号塞到线段树离维护最大值，然后对这 2*cnt 个块由最小值从小到大进行排序，枚举每个块的最小值，然后更新答案，然后将这个块的最大值在线段树中删去，当某个块的光明状态和黑暗状态都被删去的时候，就不用继续枚举了。
1 #include<bits/stdc++.h>
2 #define ls rt << 1
3 #define rs rt << 1 | 1
4 #define lr2 (l + r) >> 1
5 #define lson l, mid, rt << 1
6 #define rson mid + 1, r, rt << 1 | 1
7 using namespace std;
8 typedef long long ll;
9 const int maxn = 5e5 + 50;
10 const int INF = 0x3f3f3f3f;
11 struct node{
12 int maxx, minn, id;
13 bool operator <(const node &b)const{
14 return minn < b.minn;
15 }
16 };
17 struct tree{
18 pair<int, int> p[2];
19 int val;
20 void deleted(int x)
21 {
22 if(p[0].first == x) p[0].second = INF;
23 else p[1].second = INF;
24 }
25 };
26 int n, m, t;
27 vector<int> G[maxn];
28 int L[maxn], D[maxn];
29 int color[maxn] , vis[maxn], cnt;
30 tree T[maxn << 2];
31 node A[maxn];
32 bool flag;
33 int num[maxn];
34 void pushup(int rt)
35 {
36 T[rt].val = max(T[ls].val, T[rs].val);
37 }
38 void build(int l, int r, int rt)
39 {
40 if(l == r)
41 {
42 T[rt].p[0] = {A[l].minn, A[l].maxx};
43 T[rt].p[1] = {A[l + cnt].minn, A[l + cnt].maxx};
44 T[rt].val = min(A[l].maxx, A[l + cnt].maxx);
45 return;
46 }
47 int mid = lr2;
48 build(lson);
49 build(rson);
50 pushup(rt);
51 }
52 void update(int k, int v, int l, int r, int rt){
53 if(l == r){
54 T[rt].deleted(v);
55 T[rt].val = min(T[rt].p[0].second, T[rt].p[1].second);
56 return;
57 }
58 int mid = lr2;
59 if(k <= mid) update(k, v, lson);
60 else update(k, v ,rson);
61 pushup(rt);
62 }
63 bool dfs(int v, int c, int id){
64 color[v] = c;
65 vis[v] = id;
66 for(int i = 0;i < G[v].size();i++)
67 {
68 int u = G[v][i];
69 if(color[u] == c) return false;
70 if(!color[u]){
71 if(!dfs(u, 3 - c, id)) return false;
72 }
73 }
74 return true;
75 }
76 void init()
77 {
78 for(int i = 0;i <= n;i++) G[i].clear();
79 fill(color, color + n + 100, 0);
80 fill(vis, vis + n + 100, 0);
81 fill(num, num + n + 100, 0);
82 cnt = 0;flag = false;
83 }
84 int main()
85 {
86 std::ios::sync_with_stdio(false);
87 cin >> t;
88 for(int cas = 1; cas <= t;cas++)
89 {
90 cin >> n >> m;
91 init();
92 for(int i = 0;i < m;i++)
93 {
94 int a, b; cin >> a >> b;
95 G[a].push_back(b);
96 G[b].push_back(a);
97 }
98 for(int i = 1;i <= n;i++) cin >> L[i] >> D[i];
99 for(int i = 1;i <= n;i++)
100 {
101 if(!vis[i])
102 {
103 ++cnt;
104 if(!dfs(i, 1, cnt))
105 {
106 flag = true;
107 break;
108 }
109 }
110 }
111 cout << "Case " << cas << ": ";
112 if(flag){
113 cout << "IMPOSSIBLE" << endl;
114 continue;
115 }
116 for(int i = 1;i <= 2 * cnt;i++)
117 {
118 A[i].maxx = 0, A[i].minn = INF;
119 }
120 for(int i = 1;i <= n;i++){
121 int x = vis[i];
122 if(color[i] == 1)
123 {
124 A[x].id = x;
125 A[x].maxx = max(A[x].maxx, L[i]);
126 A[x].minn = min(A[x].minn, L[i]);
127 A[x + cnt].id = x;
128 A[x + cnt].maxx = max(A[x + cnt].maxx, D[i]);
129 A[x + cnt].minn = min(A[x + cnt].minn, D[i]);
130 }
131 else{
132 A[x].id = x;
133 A[x].maxx = max(A[x].maxx, D[i]);
134 A[x].minn = min(A[x].minn, D[i]);
135 A[x + cnt].id = x;
136 A[x + cnt].maxx = max(A[x + cnt].maxx, L[i]);
137 A[x + cnt].minn = min(A[x + cnt].minn, L[i]);
138 }
139 }
140 build(1, cnt, 1);
141 sort(A + 1, A + 2 * cnt + 1);
142 int ans = INF;
143 for(int i = 1;i <= 2 * cnt;i++)
144 {
145 ans = min(ans, T[1].val - A[i].minn);
146 num[A[i].id]++;
147 if(num[A[i].id] == 2) break;
148 update(A[i].id, A[i].minn, 1, cnt, 1);
149 }
150 cout << ans << endl;
151 }
152 return 0;
153 }G：题目大意：在一个 n * m 的土地，要在一个子矩形内放稻草人，稻草人必须被稻草包围，问合法的方法有多少种？
问题其实可以转化为：在 n * m 的草地上，选出一块子矩形，这个子矩形来放满稻草人必须被包括在 n * m 的矩形内。可以行和列分开考虑，（行的方案数） * （列的方案数）就是答案。一行可以选 4 个点，里面两个点是子矩形的宽的边界（列的边界），发现这样能确定一个子矩形的列的情况，但还有一种遗漏，就是只有一列的子矩形，这种情况只需要选三个点，所以是 c [m][3] + c [m][4]， 这样就确定了列的所有方案，行的方案跟列的方案类似。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 1e5 + 5;
5 const int mod = 1e9 + 7;
6 ll C[maxn][5];
7 void init()
8 {
9 C[0][0] = 1;
10 for(int i = 1; i <= maxn;i++)
11 {
12 C[i][0] = 1;
13 for(int j = 1; j <= 4;j++)
14 C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
15 }
16 }
17 int main()
18 {
19 std::ios::sync_with_stdio(false);
20 int n, m ,t;
21 cin >> t;
22 init();
23 for(int cas = 1;cas <= t;cas++)
24 {
25 cin >> n >> m;
26 ll h = (C[n][3] + C[n][4]) % mod;
27 ll w = (C[m][3] + C[m][4]) % mod;
28 ll ans = h * w % mod;
29 cout << "Case "<< cas << ": ";
30 cout << ans << endl;
31 }
32 return 0;
33 }I：记录每个点的横纵坐标所在行列的点的数目，找到最大的 maxx,maxy,max_x = maxx+maxy，其实消灭蟑螂的最大数目只能是 max_x, 或者 max_x-1。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 1e5 + 5;
5 ll n;
6 map<int,int> x, y;
7 struct node{
8 int x,y;
9 };
10 node a[maxn];
11 int main()
12 {
13 std::ios::sync_with_stdio(false);
14 int t;
15 cin >> t;
16 for(int cas = 1; cas <=t; cas++){
17 cin >> n;
18 x.clear();
19 y.clear();
20 for(int i = 1; i <= n; i++){
21 cin >> a[i].x >> a[i].y;
22 x[a[i].x]++;
23 y[a[i].y]++;
24 }
25 int maxx = 0, maxy = 0;
26 for(int i = 1; i <= n; i++){
27 maxx = max(maxx, x[a[i].x]);
28 maxy = max(maxy, y[a[i].y]);
29 }
30 if(x.size() == 1 || y.size() == 1){
31 cout << "Case " << cas << ": " << n << " " << 1 << endl;
32 }
33 else{
34 if(maxx == 1 && maxy == 1){
35 cout << "Case " << cas << ": " << 2 << " " << n*(n-1)/2 << endl;
36 }
37 else{
38 ll x1 = 0, x2 = 0, y1 = 0, y2 = 0;
39 map<int,int>::iterator it;
40 for(it = x.begin(); it != x.end(); it++){
41 if(it->second == maxx) x1++;
42 else if(it->second == maxx - 1) x2++;
43 }
44 for(it = y.begin(); it != y.end(); it++){
45 if(it->second == maxy) y1++;
46 else if(it->second == maxy - 1) y2++;
47 }
48 ll ans1 = 0, ans2 = 0;
49 ans1 = x1 * y1;
50 ans2 = x2 * y1 + x1 * y2;
51 for(int i = 1; i <= n; i++){
52 if(maxx + maxy == x[a[i].x] + y[a[i].y]){
53 ans1--;
54 ans2++;
55 }
56 else if(maxx + maxy - 1 == x[a[i].x] + y[a[i].y]){
57 ans2--;
58 }
59 }
60 if(ans1){
61 cout << "Case " << cas << ": " << maxx + maxy << " " << ans1 << endl;
62 }
63 else{
64 cout << "Case " << cas << ": " << maxx + maxy - 1 << " " << ans2 << endl;
65 }
66 }
67 }
68 }
69
70
71 }L：贪心 + 分类讨论 + 暴力。小于等于 11 直接 impossible， 然后奇数可以拆成 2 2 2 3 + 偶数， 偶数可以拆成 2 2 2 2 + 偶数，对最后的偶数暴力分解即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 bool check(ll x)
5 {
6 int n = sqrt(x);
7 for(int i = 2;i <= n;i++){
8 if(x % i == 0)return false;
9 }
10 return true;
11
12 }
13 void print(ll n)
14 {
15 for(ll i = n - 2;i >= 2;i--){
16 if(check(i) && check(n - i)){
17 cout << " " << i << " " << n - i << endl;
18 return;
19 }
20 }
21 }
22 int main()
23 {
24 std::ios::sync_with_stdio(false);
25 int t;
26 cin >> t;
27 int cnt = 1;
28 while(t--)
29 {
30 ll n;
31 cin >> n;
32 cout << "Case "<< cnt++ <<": ";
33 if(n > 11)
34 {
35 if(n & 1)
36 {
37 n -= 9LL;
38 cout << "2 2 2 3";
39 print(n);
40 }
41 else{
42 n -= 8LL;
43 cout << "2 2 2 2";
44 print(n);
45 }
46 }
47 else cout << "IMPOSSIBLE" << endl;
48 }
49 return 0;
50 }
2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) Solution
A. Altruistic Amphibians
Upsolved.
题意：
$ 有 n 只青蛙，其属性用三元组表示 <l_i, w_i, h_i> l_i 是它能跳的高度，w_i 是它的体重，h_i 是它的身高 $
一只青蛙的承重不能超过它的体重，它可以踩在别的青蛙上面跳
一口井的深度为 $d， 一只青蛙能够跳出去当且仅当它离井口的距离严格小于它的 l_i$
$ 离井口的距离为 d - 它所踩的青蛙的身高和，当然可以不踩其他青蛙 $
求最多跳出去多少只青蛙
思路：
显然，重量最大的青蛙肯定只能在最下面
那么按重量大小排个序
然后考虑递推到下面
$dp [i] 表示 重量为 i 的青蛙最高能处在什么样的高度 $
有
$dp[j - a[i].w] = dp[j] +a[i].h \;\;j \in [a[i].w, 2 * a[i].w)$
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 100010
6 const int D = (int)1e8 + 10;
7 int n, d;
8 struct node
9 {
10 int l, w, h;
11 void scan() { scanf("%d%d%d", &l, &w, &h); }
12 bool operator < (const node &r) const { return w > r.w; }
13 }a[N];
14 int dp[D];
15
16 int main()
17 {
18 while (scanf("%d%d", &n, &d) != EOF)
19 {
20 for (int i = 1; i <= n; ++i) a[i].scan();
21 sort(a + 1, a + 1 + n);
22 int res = 0;
23 for (int i = 1; i <= n; ++i)
24 {
25 if (dp[a[i].w] + a[i].l > d) ++res;
26 for (int j = a[i].w; j < min(2 * a[i].w, (int)1e8 + 2); ++j)
27 dp[j - a[i].w] = max(dp[j - a[i].w], dp[j] + a[i].h);
28 }
29 printf("%d\n", res);
30 }
31 return 0;
32 }
B. Baby Bites
Solved.
签到。
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int n;
5 int pre, now;
6 string s;
7
8 int f()
9 {
10 if (s == "mumble") return -1;
11 int res = 0;
12 for (int i = 0, len = s.size(); i < len; ++i) res = res * 10 + s[i] - ''0'';
13 return res;
14 }
15
16 bool solve()
17 {
18 bool flag = 1;
19 pre = 0;
20 for (int i = 1; i <= n; ++i)
21 {
22 cin >> s;
23 now = f();
24 if (now == -1) ++pre;
25 else if (now != pre + 1) flag = 0;
26 else pre = now;
27 }
28 return flag;
29 }
30
31 int main()
32 {
33 ios::sync_with_stdio(false);
34 cin.tie(0); cout.tie(0);
35 while (cin >> n) cout << (solve() ? "makes sense" : "something is fishy") << "\n";
36 return 0;
37 }
C. Code Cleanups
Solved.
签到。
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 int n;
6 int vis[400];
7
8 int main()
9 {
10 while(~scanf("%d", &n))
11 {
12 memset(vis, 0, sizeof vis);
13 for(int i = 1, num; i <= n; ++i)
14 {
15 scanf("%d", &num);
16 vis[num]++;
17 }
18 int ans = 0;
19 int tmp = 0;
20 int pre = 0;
21 for(int i = 1; i <= 365; ++i)
22 {
23 tmp += vis[i];
24 pre += tmp;
25 if(pre >= 20)
26 {
27 ++ans;
28 pre = 0;
29 tmp = 0;
30 }
31 }
32 if(pre) ans++;
33 printf("%d\n", ans);
34 }
35 return 0;
36 }
D. Delivery Delays
Upsolved.
题意：
有一张无向图，顶点 1 有一家披萨店，时不时会有一点发布订单表示它在 $s_i 时刻要一份披萨，这份披萨要在 t_i 时刻才能好 $
$ 只有一个送货员，必须满足先到先服务的原则，如何安排送货流程使得等待时间最长的顾客的等待时间最短 $
思路：
先预处理出任意两点之间的最短路径，再考虑二分答案
$ 用 dp 验证 $
$dp [i][j][k] 表示已经送完前 i 个点，拿到前 j 个披萨，k \in [0, 1]$
$0 表示 目前处于第 i 个点，1 表示目前处于披萨店 $
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 1010
6 #define INFLL 0x3f3f3f3f3f3f3f3f
7 struct Graph
8 {
9 struct node
10 {
11 int to, nx, w;
12 node () {}
13 node (int to, int nx, int w) : to(to), nx(nx), w(w) {}
14 }a[N << 5];
15 int head[N], pos;
16 void init()
17 {
18 memset(head, -1, sizeof head);
19 pos = 0;
20 }
21 void add(int u, int v, int w)
22 {
23 a[++pos] = node(v, head[u], w); head[u] = pos;
24 a[++pos] = node(u, head[v], w); head[v] = pos;
25 }
26 }G;
27 #define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; ~it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)
28
29 int n, m, q;
30 ll dist[N][N];
31 namespace Dij
32 {
33 struct node
34 {
35 int to; ll w;
36 node () {}
37 node (int to, ll w) : to(to), w(w) {}
38 bool operator < (const node &r) const { return w > r.w; }
39 };
40 bool used[N];
41 void run()
42 {
43 for (int st = 1; st <= n; ++st)
44 {
45 for (int i = 1; i <= n; ++i) dist[st][i] = INFLL, used[i] = false;
46 priority_queue <node> q; q.emplace(st, 0); dist[st][st] = 0;
47 while (!q.empty())
48 {
49 int u = q.top().to; q.pop();
50 if (used[u]) continue;
51 used[u] = 1;
52 erp(u) if (!used[v] && dist[st][v] > dist[st][u] + w)
53 {
54 dist[st][v] = dist[st][u] + w;
55 q.emplace(v, dist[st][v]);
56 }
57 }
58 }
59 }
60 }
61
62 ll dp[N][N][2];
63 // dp[i][j][0] 表示已经送完前i个点，拿到前j个披萨，目前处于第i个点的最小时间
64 // dp[i][j][1] 表示已经送完前i个点，拿到前j个披萨，目前处于披萨店的最小时间
65 int s[N], u[N], t[N];
66 bool check(ll x)
67 {
68 memset(dp, 0x3f, sizeof dp);
69 dp[0][0][1] = 0;
70 for (int i = 0; i < q; ++i)
71 {
72 for (int j = i; j <= q; ++j)
73 {
74 for (int o = 0; o < 2; ++o)
75 {
76 if (!o)
77 {
78 dp[i][j][1] = min(dp[i][j][1], dp[i][j][0] + 1ll * dist[u[i]][1]);
79 if (j > i)
80 {
81 ll T = dp[i][j][0] + dist[u[i]][u[i + 1]];
82 if (s[i + 1] + x >= T)
83 dp[i + 1][j][0] = min(dp[i + 1][j][0], T);
84 }
85 }
86 else
87 {
88 if (j < q)
89 dp[i][j + 1][1] = min(dp[i][j + 1][1], max(dp[i][j][1], 1ll * t[j + 1]));
90 if (j > i)
91 {
92 ll T = dp[i][j][1] + dist[1][u[i + 1]];
93 if (s[i + 1] + x >= T)
94 dp[i + 1][j][0] = min(dp[i + 1][j][0], T);
95 }
96 }
97 }
98 }
99 }
100 return dp[q][q][0] != INFLL;
101 }
102
103 int main()
104 {
105 while (scanf("%d%d", &n, &m) != EOF)
106 {
107 G.init();
108 for (int i = 1, u, v, w; i <= m; ++i)
109 {
110 scanf("%d%d%d", &u, &v, &w);
111 G.add(u, v, w);
112 }
113 Dij::run();
114 scanf("%d", &q);
115 for (int i = 1; i <= q; ++i) scanf("%d%d%d", s + i, u + i, t + i);
116 ll l = 0, r = INFLL, res = -1;
117 while (r - l >= 0)
118 {
119 ll mid = (l + r) >> 1;
120 if (check(mid))
121 {
122 res = mid;
123 r = mid - 1;
124 }
125 else
126 l = mid + 1;
127 }
128 printf("%lld\n", res);
129 }
130 return 0;
131 }
E. Explosion Exploit
Solved.
题意：
你有 $n 个随从，对方有 m 个随从，你现在可以发动一个技能，造成 d 点伤害 $
$ 每点伤害都会等概率的下落到敌方的随从身上，求发动一次技能，敌方随从全部死亡的概率 $
思路：
概率记忆化搜索
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 typedef long long ll;
6
7 int n, m, d;
8 int sum[3][10];
9 map <ll, double>dp;
10
11 ll calc()
12 {
13 ll res = 0;
14 for(int i = 1; i <= 6; ++i)
15 {
16 res += sum[0][i];
17 res *= 10;
18 }
19 for(int i = 1; i <= 6; ++i)
20 {
21 res += sum[1][i];
22 res *= 10;
23 }
24 return res;
25 }
26
27 double DFS(ll S, int limit)
28 {
29 if(dp.count(S)) return dp[S];
30 int cnt = 0;
31 for(int i = 1; i <= 6; ++i) cnt += sum[1][i];
32 if(!cnt) return 1;
33 if(limit == 0) return 0;
34 for(int i = 1; i <= 6; ++i) cnt += sum[0][i];
35 double res = 0;
36 for(int i = 0; i < 2; ++i)
37 {
38 for(int j = 1; j <= 6; ++j)
39 {
40 if(sum[i][j] == 0) continue;
41 sum[i][j]--;
42 sum[i][j - 1]++;
43 double tmp = DFS(calc(), limit - 1);
44 sum[i][j]++;
45 sum[i][j - 1]--;
46 res += 1.0 * sum[i][j] / cnt * tmp;
47 }
48 }
49 dp[S] = res;
50 return res;
51 }
52
53 int main()
54 {
55 while(~scanf("%d %d %d", &n, &m, &d))
56 {
57 dp.clear();
58 memset(sum, 0, sizeof sum);
59 for(int i = 1, num; i <= n; ++i)
60 {
61 scanf("%d", &num);
62 sum[0][num]++;
63 }
64 for(int i = 1, num; i <= m; ++i)
65 {
66 scanf("%d", &num);
67 sum[1][num]++;
68 }
69 double ans = DFS(calc(), d);
70 printf("%.10f\n", ans);
71 }
72 return 0;
73 }
F. Firing the Phaser
Unsolved.
G. Game Scheduling
Unsolved.
H. House Lawn
Solved.
题意：
有一些割草机，工作一段时间，休息一段时间
求哪些机器在 T 周至少割草 T 次，如果有，按输入顺序输出价格最低的
思路：
因为 $ 周期是 LCM (t + r, 10080), 如果这个周期内是可以的，那就是可以的 $
因为如果中间有一周割不完了，那么后面肯定是割不完的
因为开始的局面相当于满电让你割，那么对于后面的情况
每周平均割草的次数肯定小于等于前面的
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 110
5 #define ll long long
6
7 ll l; int m;
8 ll Min;
9
10 ll gcd(ll a, ll b)
11 {
12 return b == 0 ? a : gcd(b, a % b);
13 }
14
15 ll lcm(ll a, ll b)
16 {
17 return a * b / gcd(a, b);
18 }
19
20 struct qnode
21 {
22 string name;
23 ll p, c, t, r;
24 bool flag;
25 void scan()
26 {
27 flag = false;
28 p = 0, c = 0, t = 0, r = 0;
29 name = "";
30 string s;
31 getline(cin, s);
32 int i, len = s.size();
33 for (i = 0; s[i] != '',''; ++i)
34 name += s[i];
35 for (++i; s[i] != '',''; ++i) p = p * 10 + s[i] - ''0'';
36 for (++i; s[i] != '',''; ++i) c = c * 10 + s[i] - ''0'';
37 for (++i; s[i] != '',''; ++i) t = t * 10 + s[i] - ''0'';
38 for (++i; i < len; ++i) r = r * 10 + s[i] - ''0'';
39 //cout << p << " " << c << " " << t << " " << r << endl;
40 }
41 void f()
42 {
43 ll need = l % (c * t) == 0 ? l / (c * t) : l / (c * t) + 1;
44 ll remind = 0;
45 if (l % (c * t)) remind = t - (l - (c * t) * (need)) % c;
46 ll tot = need * (t + r);
47 tot -= remind;
48 flag = tot <= 10080;
49 if (flag) Min = min(Min, p);
50 }
51 void F4()
52 {
53 flag = false;
54 ll circle = lcm(t + r, 10080);
55 ll T = circle / 10080;
56 if(circle / (t + r) * c * t>= T * l)
57 {
58 flag = true;
59 Min = min(Min, p);
60 }
61 }
62 }qarr[N];
63
64 int main()
65 {
66 ios::sync_with_stdio(false);
67 cin.tie(0); cout.tie(0);
68 while (cin >> l >> m)
69 {
70 string s;
71 getline(cin, s);
72 Min = 0x3f3f3f3f3f3f3f3f;
73 for (int i = 1; i <= m; ++i) qarr[i].scan(), qarr[i].F4();
74 vector <string> res;
75 for (int i = 1; i <= m; ++i) if (qarr[i].flag && qarr[i].p == Min) res.push_back(qarr[i].name);
76 for (auto it : res) cout << it << "\n";
77 if (res.empty()) cout << "no such mower\n";
78 }
79 return 0;
80 }
I. Intergalactic Bidding
Solved.
简单模拟。
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 1010
5 #define DLEN 4
6 #define MAXN 9999
7 int n;
8
9 class BigNum
10 {
11 private:
12 int a[N];
13 int len;
14 public:
15 BigNum() { len = 1; memset(a, 0, sizeof a); }
16 BigNum(const char *s)
17 {
18 int t, k, index, L, i;
19 memset(a, 0, sizeof a);
20 L = strlen(s);
21 len = L / DLEN;
22 if (L % DLEN) ++len;
23 index = 0;
24 for (int i = L - 1; i >= 0; i -= DLEN)
25 {
26 t = 0;
27 k = i - DLEN + 1;
28 if (k < 0) k = 0;
29 for (int j = k; j <= i; ++j)
30 t = t * 10 + s[j] - ''0'';
31 a[index++] = t;
32 }
33 }
34 bool operator == (const BigNum &T) const
35 {
36 if (len != T.len) return false;
37 for (int i = 0; i < len; ++i) if (a[i] != T.a[i])
38 return false;
39 return true;
40 }
41 bool operator < (const BigNum &T) const
42 {
43 if (len != T.len) return len < T.len;
44 for (int i = len - 1; i >= 0; --i) if (a[i] != T.a[i])
45 return a[i] < T.a[i];
46 return true;
47 }
48 BigNum& operator = (const BigNum &n)
49 {
50 int i;
51 len = n.len;
52 memset(a, 0, sizeof a);
53 for (int i = 0; i < len; ++i) a[i] = n.a[i];
54 return *this;
55 }
56 BigNum operator - (const BigNum &T) const
57 {
58 int i, j, big;
59 BigNum t1, t2;
60 t1 = *this, t2 = T;
61 big = t1.len;
62 for (i = 0; i < big; ++i)
63 {
64
65 if (t1.a[i] < t2.a[i])
66 {
67 j = i + 1;
68 while (t1.a[j] == 0) ++j;
69 t1.a[j--]--;
70 while (j > i) t1.a[j--] += MAXN;
71 t1.a[i] += MAXN + 1 - t2.a[i];
72 }
73 else t1.a[i] -= t2.a[i];
74 }
75 t1.len = big;
76 while (t1.a[t1.len - 1] == 0 && t1.len > 1)
77 {
78 t1.len--;
79 big--;
80 }
81 return t1;
82 }
83 void print()
84 {
85 cout << a[len - 1];
86 for (int i = len - 2; i >= 0; --i)
87 printf("%04d", a[i]);
88 puts("");
89 }
90 };
91
92 char str[N];
93 BigNum s;
94
95 struct node
96 {
97 string name;
98 BigNum val;
99 void scan()
100 {
101 cin >> name;
102 cin >> str;
103 val = BigNum(str);
104 }
105 bool operator < (const node &r) { return r.val < val; }
106 }arr[N];
107
108 vector <string> res;
109 int main()
110 {
111 ios::sync_with_stdio(false);
112 cin.tie(0); cout.tie(0);
113 while (cin >> n)
114 {
115 res.clear();
116 cin >> str; s = BigNum(str);
117 for (int i = 1; i <= n; ++i) arr[i].scan();
118 sort(arr + 1, arr + 1 + n);
119 for (int i = 1; i <= n; ++i) if (arr[i].val < s)
120 {
121 s = s - arr[i].val;
122 res.push_back(arr[i].name);
123 }
124 if (!(s == BigNum("0"))) cout << "0\n";
125 else
126 {
127 cout << res.size() << "\n";
128 for (auto it : res) cout << it << "\n";
129 }
130 }
131 return 0;
132 }
J. Jumbled String
Solved.
题意：
要求构造一个 01 串，使得所有子序列中，$00 出现 a 次，01 出现 b 次，10 出现 c 次，11 出现 d 次 $
思路：
显然，如果 $a > 0, b > 0， 那么其中 0 的个数和 1 的个数是固定的 $
而且有 $b + c == cnt [0] \cdot cnt [1]$
$ 此处 cnt 表示 0 的个数或者 1 的个数 $
$ 那么刚开始 0 全放全面，1 全放后面，然后把 1 往前面挪动，直到满足条件 $
记得特判几种特殊情况以及 $Impossible$
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 ll a, b, c, d;
6 ll n, m, need, remind;
7
8 ll f(ll x)
9 {
10 for (ll i = 1; ; ++i)
11 {
12 if ((i * (i - 1) / 2) > x) return -1;
13 if (i * (i - 1) / 2 == x) return i;
14 }
15 }
16
17 int main()
18 {
19 while (scanf("%lld%lld%lld%lld", &a, &b, &c, &d) != EOF)
20 {
21 if (!a && !b && !c && !d) puts("0");
22 else if (!b && !c && !d)
23 {
24 n = f(a);
25 if (n == -1) puts("impossible");
26 else
27 {
28 for (int i = 1; i <= n; ++i) putchar(''0'');
29 puts("");
30 }
31 }
32 else if (!a && !b && !c)
33 {
34 m = f(d);
35 if (m == -1) puts("impossible");
36 else
37 {
38 for (int i = 1; i <= m; ++i) putchar(''1'');
39 puts("");
40 }
41 }
42 else
43 {
44 n = f(a), m = f(d);
45 if (n == -1 || m == -1 || n * m != (b + c)) puts("impossible");
46 else
47 {
48 need = b / n;
49 remind = b % n;
50 for (int i = 1; i <= m - need - (remind ? 1 : 0); ++i) putchar(''1'');
51 for (int i = 1; i <= n; ++i)
52 {
53 putchar(''0'');
54 if (i == remind) putchar(''1'');
55 }
56 for (int i = 1; i <= need; ++i) putchar(''1'');
57 puts("");
58 }
59 }
60 }
61 return 0;
62 }
K. King''s Colors
Solved.
题意：
给出一棵树，相邻结点不能染相同颜色，求恰好染 k 种颜色的方案数。
思路：
因为是一棵树，那么如果所求的是 $<=k 种颜色的方案数 答案就是 k * (k - 1)^ {n -1}$
$ 因为根节点有 k 种选择，其他结点都有 k - 1 种选择 $
但实际上这包含了 $k - 2, k - 3, k - 4 \cdots 2 的方案数 容斥一下即可 $
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 typedef long long ll;
6
7 const int maxn = 2510;
8 const ll MOD = 1e9 + 7;
9
10 ll fac[maxn], invfac[maxn], inv[maxn];
11
12 ll qpow(ll x,ll n)
13 {
14 ll res = 1;
15 while(n)
16 {
17 if(n & 1) res = res * x % MOD;
18 x = x * x % MOD;
19 n >>= 1;
20 }
21 return res;
22 }
23
24 void Init()
25 {
26 fac[0] = invfac[0] = inv[0] = 1;
27 fac[1] = invfac[1] = inv[1] = 1;
28 for(int i = 2; i < maxn; ++i)
29 {
30 fac[i] = fac[i - 1] * i % MOD;
31 inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
32 invfac[i] = invfac[i - 1] * inv[i] % MOD;
33 }
34 }
35
36 ll calc(int n, int m)
37 {
38 if (n < 0 || m < 0) return 0;
39 if (n == m || m == 0) return 1;
40 return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
41 }
42
43 int n, k;
44
45 int main()
46 {
47 Init();
48 while(~scanf("%d %d",&n, &k))
49 {
50 for(int i = 1, num; i < n; ++i) scanf("%d", &num);
51 int flag = 1;
52 ll ans = 0;
53 for(int i = k; i >= 2; --i, flag = !flag)
54 {
55 if(flag) ans = (ans + calc(k, i) * i % MOD * qpow(i - 1, n - 1) % MOD) % MOD;
56 else ans = (ans - calc(k, i) * i % MOD * qpow(i - 1, n - 1) % MOD + MOD) % MOD;
57 }
58 printf("%lld\n", ans);
59 }
60 return 0;
61 }
2018-2019赛季多校联合新生训练赛第三场(2018/12/8)补题题解
感慨
得复习回溯和dfs了。。。
A 变形虫（语法基础）
代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> num;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>num[i];
for(int i=0;i<m;i++)
if(num[i]==n)
n+=num[i];
cout<<n;
}
B 冬眠 （数学）
注意避免超时先找一下最后在周期内的哪一个位置
代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> num;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,t=0,sum=0,re=0;
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>num[i],re+=num[i];
sum+=m*(n/re);
n%=re;
while(n>0)
{
n-=num[t];
t++;
t%=m;
sum++;
}
cout<<sum;
}
C 进制转换 （语法基础）
我的思路是先化成十进制，再按照栈的思想化成各种进制。。。这估计也不是正解
代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> sum;
stack <char> st;
int qb(int a,int b)
{
int re=1;
for(int i=0;i<b;i++)
re*=a;
return re;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,sum=0;
cin>>n;
string a;
cin>>a;
int len=a.size();
for(int i=0;i<len;i++)
{
if(a[i]==''A'')
sum+=10*qb(n,len-i-1);
else if(a[i]==''B'')
sum+=11*qb(n,len-i-1);
else if(a[i]==''C'')
sum+=12*qb(n,len-i-1);
else if(a[i]==''D'')
sum+=13*qb(n,len-i-1);
else if(a[i]==''E'')
sum+=14*qb(n,len-i-1);
else if(a[i]==''F'')
sum+=15*qb(n,len-i-1);
else
sum+=(a[i]-''0'')*qb(n,len-i-1);
}
int m;
cin>>m;
while(sum)
{
int t=sum%m;
char c;
if(t==10)
c=''A'';
else if(t==11)
c=''B'';
else if(t==12)
c=''C'';
else if(t==12)
c=''C'';
else if(t==13)
c=''D'';
else if(t==14)
c=''E'';
else if(t==15)
c=''F'';
else if(t<10)
c=char(t+''0'');
sum/=m;
st.push(c);
}
while(st.size())
{
cout<<st.top();
st.pop();
}
}
D 最大的数II （数学）
找一下递推式，判断一下条件即可
代码
#include <bits/stdc++.h>
using namespace std;
map<int,int> sum;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,t=0,re=0;
cin>>n;
for(int i=1;i<=100000;i++)
sum[i]=i+sum[i-1];
for(int i=1;;i++)
{
if(sum[i]>n)
{
cout<<i-1;
break;
}
else if(sum[i]==n)
{
cout<<i;
break;
}
}
}
E 取数排列 （全排列）
打个全排列抽一下数即可
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
/*ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);*/
int n,m,sum=0;
cin>>n>>m;
for(int i=0;i<n;i++)
bk[i]=i+1;
do {
sum++;
if(sum==m)
{
for(int i=0;i<n;i++)
{
cout<<bk[i];
}
break;
}
} while(next_permutation(bk,bk+n));
}
F 懒羊羊找朋友 （结构体排序）
解法
首先要找距离
公式为：|xi-x|+|yi-y|
然后把所有的相同数的点的距离算出来之后，再按照他给的条件排个序输出即可
代码
#include <bits/stdc++.h>
using namespace std;
int mp[1000][1000];
struct node
{
int x,y,dis;
}bk[1000000];
bool cmp(node a,node b)
{
return a.dis==b.dis?a.x==b.x?a.y<b.y:a.x<b.x:a.dis<b.dis;
}
int main()
{
/*ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);*/
int n,m,x,y,p=0;
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]==mp[x][y])
{
if(i==x&&j==y)
continue;
bk[p].x=i,bk[p].y=j,bk[p++].dis=abs(i-x)+abs(j-y);
}
sort(bk,bk+p,cmp);
cout<<bk[0].x<<" "<<bk[0].y;
}
G 求满足条件的数 （语法基础）
代码
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int bk[100000];
char c[10000];
int main()
{
/*ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);*/
int n,tot=0;
cin>>n;
for(int i=69;i<=n;i++)
{
stringstream s;
s<<i;
string ss;
s>>ss;
int sum=0;
for(int i=0;i<ss.size();i++)
sum+=ss[i]-''0'';
if(sum==15)
printf("%6d",i),tot++;
if(tot==8)
printf("\n"),tot=0;
}
}
H 自然数无序拆分 （DFS）
这里还需要打表才可以接受。。。如果用dfs的话。
首先我们得确定dfs中要有几个变量，sum和cur肯定是必不可少的吧。一个是总和一个是当前的进行的步骤
但是我们观察发现如果要去重的话，那么还需要保证下一位比上一位还要大，那么还需要一个记录上一位大小的变量now。剩下的就基本一目了然了
只需要枚举一下位数即可
代码（打表程序）
#include <bits/stdc++.h>
using namespace std;
int n,ans,k;
void dfs(int now,int sum,int cur)
{
if(cur==k)
{
if(sum==n)
ans++;
}
else
{
for(int i=now;sum+i*(k-cur)<=n;i++)
dfs(i,sum+i,cur+1);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
k=i;
dfs(1,0,0);
}
cout<<ans;
}
这里解释一下这个剪枝的问题，因为100过于庞大，所以一般的打表会很慢很慢，那么我们需要进行剪纸。那么我们就要计算一下如果之后的位数全是当前位数的话，答案加起来还比原先的数大，那么就没有必要再搜索了，因为搜索的之后的数一定比原来的数大，原来的数都不能满足小于n，还求别的数小于n？
I 大写字母的序列 （语法基础）
代码
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int bk[100000];
char c[10000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=0;i<3;i++)
cin>>sum[i];
for(int i=0;i<3;i++)
cin>>c[i];
sort(sum,sum+3);
bk[''A'']=sum[0];
bk[''B'']=sum[1];
bk[''C'']=sum[2];
for(int i=0;i<3;i++)
cout<<bk[c[i]]<<" ";
}
J 弗洛格 （语法基础）
代码
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int bk[100000];
char c[10000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
if(n<=26)
cout<<27-n;
else if(n>26)
{
n-=26;
cout<<30-n+1;
}
}
K 移动次数最少 （贪心）
洛谷试炼场的原题。。。原题好像是叫做移动纸牌。
解法
因为这里最左边的不能和最右边的联系。所以只有中间的那些能够左右的交换。
两个变量很麻烦，我们直接设置一个移动变量xi代表移动的卡牌数目
例如x1代表1给2的卡牌数
xi=ai-avg（ai代表当前手中的卡牌，avg代表平均最终的卡牌数）
线性扫描一下如果当前的牌经过之前的移动还不是avg的话那么答案加一次
最后输出即可
代码
#include <bits/stdc++.h>
using namespace std;
int num[1000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,re=0,sum=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>num[i],sum+=num[i];
int avr=sum/n;
for(int i=0;i<n-1;i++)
{
if(num[i]!=avr)
{
re++;
num[i+1]+=num[i]-avr;
}
}
cout<<re;
}
L 小矮人 （语法基础）
代码
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int bk[100000];
char c[10000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=0;i<6;i++)
{
int t;
cin>>t;
bk[t]++;
}
for(int i=1;i<=7;i++)
if(!bk[i])
cout<<i;
}
M 小米 （语法基础）
代码
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int bk[100000];
char c[10000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int f,m,me;
cin>>f>>m>>me;
if(me==1)
cout<<(f+m+13)/2;
else if(me==0)
cout<<(f+m-13)/2;
}
N 小球 （思维）
直接把所有的情况拿出来做个比较即可
解法
经过观察，我们发现如果要把一个红球放到蓝箱子里那么一定需要把一个蓝球放到红箱子里
那么这里肯定只有三种情况
①红球放到红箱子，蓝球放到蓝箱子
②红球或者蓝球数量少的全部放到另一个箱子，其他的还在原来的相同颜色的箱子内
③红球蓝球数量相等全部互换
为什么不可能有部分的情况？
因为移动或者不移动肯定会有一个价值的变化，而这个变化肯定也只有变大或者变小，不可能说你移动部分之后就会比移动全部的要变化的好
代码
#include <bits/stdc++.h>
using namespace std;
int num[1000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a,b,c,d,e;
cin>>a>>b>>c>>d>>e;
int r1=a*c+b*d;
int r2;
if(a>b)
r2=2*b*e+(a-b)*c;
else if(a<b)
r2=2*a*e+(b-a)*d;
else
r2=2*a*e;
cout<<max(r1,r2);
}
O 找最长良序字符串 （字符串基础）
数据太小了，直接暴力就行了
代码
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int bk[100000];
char c[10000];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string a;
cin>>a;
int re=-1;
for(int i=0;i<a.size();i++)
{
char t=a[i];
int sum=1;
for(int j=i+1;j<a.size();j++)
{
if(a[j]>t)
sum++,t=a[j];
else
break;
}
re=max(re,sum);
}
cout<<re;
}
今天关于mysql 基础一，续 2018-10-23和mysql基础教程的讲解已经结束，谢谢您的阅读，如果想了解更多关于1，Django 基础一、2018 China Collegiate Programming Contest Final (CCPC-Final 2018)(A B G I L)、2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) Solution、2018-2019赛季多校联合新生训练赛第三场(2018/12/8)补题题解的相关知识，请在本站搜索。
本文标签：
