题意:
定义,有可能获得冠军:没输过的人
题解:遍历一遍所有输赢情况,只要输过就标记一下,最后查找没有被标记的都是有可能获得冠军的人。
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 100050;
int a[N];
void init() {
for (int i = 0; i < N; i++) {
a[i] = 1;
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
init();
while (m--) {
int x, y;
cin >> x >> y;
a[y] = 0;
}
int count = 0;
for (int i = 1; i <= n; i++) {
if (a[i]) count++;
}
cout << count << endl;
return 0;
}
跑是隔一个能吃(这应该都知道吧~~~)
如果说只有一行,只要这一行超过了3个,就存在 “跑隔一个能吃” 的情况,所以一行最少能剩余2个跑。
那么同理,一列最少能剩余2个跑。所以最少能剩余4个跑。
特殊情况:
x == 1 且 y == 1,剩余1个炮
x == 1 且 y > 1,剩余2个炮
其他情况都是剩余4个炮,注意一下n, m的数据范围,记得开long long
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int _;
cin >> _;
while (_--) {
int x, y;
cin >> x >> y;
if (x > y) swap(x, y);
if (x == 1 && y == 1) cout << 1 << endl;
else if (x == 1 && y > 1) cout << 2 << endl;
else cout << 4 << endl;
}
return 0;
}
经典DFS和BFS迷宫问题
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
bool st[N][N];
int dx[4] = {
-1, 0, 1, 0}, dy[4] = {
0, 1, 0, -1};
int n, m;
int cnt;
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a <= n + 1 && b >= 0 && b <= m + 1 && g[a][b] != '1') {
if (g[a][b] == '0') cnt++;
g[a][b] = '1';
dfs(a, b);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
dfs(0, 0);
cout << cnt << endl;
return 0;
}
太卷了吧 …
经典线段树模板题
重点在:所有值小于等于x的数字都加上x,区间修改。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
//#define int ll
#define inf 0x3f3f3f3f
using namespace std;
int gcd(int x,int y) {
if(x<y) swap(x,y);//很多人会遗忘,大数在前小数在后
//递归终止条件千万不要漏了,辗转相除法
return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y) {
return x * y / gcd(x, y); }
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 100010;
int num[N << 2];
struct Node{
int l, r;//左端点,右端点
int val;//区间[l, r]的最大值
}tr[N << 2];
int n, m, x;
//由子节点的信息来计算父节点的信息
void pushup(int cur){
//父节点是两个子节点的和,一直往上传值,就能使根节点是所有人的个数
tr[cur].val = min(tr[cur << 1].val, tr[cur << 1 | 1].val);
}
//cur代表当前节点,
void build(int cur, int l, int r){
//建树的初始值
tr[cur].l = l, tr[cur].r = r;
//如果已经是叶结点return
if(l == r) {
tr[cur].val = num[l];//如果到达叶节点就把人数赋给该节点
return;
}
//否则求一下当前区间的中点
int mid = l + r >> 1;
//递归建立左边区间
build(cur << 1, l, mid);
//递归建立右边区间
build(cur << 1 | 1, mid + 1, r);
//将子节点的人数进行汇总,给父节点
pushup(cur);
}
//[l, r]查询区间 cur代表当前线段树里面的端点。
int query(int cur, int ql, int qr) {
int l = tr[cur].l, r = tr[cur].r;
if (ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return tr[cur].val;
int mid = l + r >> 1;
int val = 0;
//判断与左边有交集
if (ql <= mid) val += query(cur << 1, ql, qr);//求和
//这里为什么是 qr > mid,因为划分的区间是[l, mid][mid + 1, r],所以要用>而不能=
//判断与右边有交集
if (qr > mid) val += query(cur << 1 | 1, ql, qr);//求和
//返回结果
return val;
}
//cur代表当前线段树里面的端点。tar代表要修改的位置,即目标位置
void modify(int l, int r, int cur, int val) {
if (l > tr[cur].r || tr[cur].l > r) return;
if (tr[cur].l == tr[cur].r) {
tr[cur].val += val;
return;
}
if (val >= tr[cur << 1].val) modify(l, r, cur << 1, val);
if (val >= tr[cur << 1 | 1].val) modify(l, r, cur << 1 | 1, val);
//递归完之后,要更新到父节点。
//pushup就是更新父节点的信息
pushup(cur);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> num[i];
build(1, 1, n);
while (m--) {
cin >> x;
if (x == 0) continue;
modify(1, n, 1, x);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = query(1, i, i);
cout << ans << ' ';
}
cout << endl;
return 0;
}
a [ i ] = = C n − 1 i 即 ∑ i = 0 n − 1 i 2 × a [ i ] = = ∑ i = 0 n − 1 i 2 × C n − 1 i a[i] == C_{n-1}^i 即 \sum_{i = 0}^{n - 1} i^2 × a[i] == \sum_{i = 0}^{n - 1} i^2 × C_{n-1}^i a[i]==Cn−1i即∑i=0n−1i2×a[i]==∑i=0n−1i2×Cn−1i
已知: ∑ i = 0 n C n i = 2 n \sum_{i=0}^{n}C_n^i = 2^n ∑i=0nCni=2n , k C n k = n C n − 1 k − 1 kC_n^k = nC_{n-1}^{k-1} kCnk=nCn−1k−1
∑ i = 0 n − 1 i 2 × C n − 1 i \sum_{i = 0}^{n - 1} i^2 × C_{n-1}^i ∑i=0n−1i2×Cn−1i
= ∑ i = 0 n − 1 i × i × C n − 1 i =\sum_{i = 0}^{n - 1} i × i × C_{n-1}^i =∑i=0n−1i×i×Cn−1i
= ∑ i = 0 n − 1 i × ( n − 1 ) × C n − 2 i − 1 = \sum_{i=0}^{n-1} i × (n-1) × C_{n-2}^{i-1} =∑i=0n−1i×(n−1)×Cn−2i−1
= ( n − 1 ) × ∑ i = 0 n − 1 ( i − 1 + 1 ) × C n − 2 i − 1 =(n-1) × \sum_{i=0}^{n-1}(i-1+1)×C_{n-2}^{i-1} =(n−1)×∑i=0n−1(i−1+1)×Cn−2i−1
= ( n − 1 ) × ∑ i = 1 n = 1 C n − 2 i − 1 + ( n − 1 ) × ∑ i = 1 n − 1 ( i − 1 ) C n − 2 i − 1 =(n-1) × \sum_{i=1}^{n=1}C_{n-2}^{i-1}+(n-1)×\sum_{i=1}^{n-1}(i-1)C_{n-2}^{i-1} =(n−1)×∑i=1n=1Cn−2i−1+(n−1)×∑i=1n−1(i−1)Cn−2i−1
= ( n − 1 ) ( C n − 2 0 + C n − 2 1 + C n − 2 2 + . . . + C n − 2 n − 1 + C n − 2 n − 2 ) + ( n − 1 ) [ ( n − 2 ) C n − 3 0 + ( n − 2 ) C n − 3 1 + . . . + ( n − 2 ) C n − 3 n − 3 ] =(n-1)(C_{n-2}^0+C_{n-2}^1+C_{n-2}^2+...+C_{n-2}^{n-1}+C_{n-2}^{n-2}) + (n-1)[(n-2)C_{n-3}^0+(n-2)C_{n-3}^1+...+(n-2)C_{n-3}^{n-3}] =(n−1)(Cn−20+Cn−21+Cn−22+...+Cn−2n−1+Cn−2n−2)+(n−1)[(n−2)Cn−30+(n−2)Cn−31+...+(n−2)Cn−3n−3]
= ( n − 1 ) ∑ i = 0 n − 2 C n − 2 i + ( n − 1 ) ( n − 2 ) ∑ i = 0 n − 3 C n − 3 i =(n-1)\sum_{i=0}^{n-2}C_{n-2}^{i} + (n-1)(n-2)\sum_{i=0}^{n-3}C_{n-3}^i =(n−1)∑i=0n−2Cn−2i+(n−1)(n−2)∑i=0n−3Cn−3i
= ( n − 1 ) 2 n − 2 + ( n − 1 ) ( n − 2 ) 2 n − 3 =(n-1)2^{n-2} + (n-1)(n-2)2^{n-3} =(n−1)2n−2+(n−1)(n−2)2n−3
= ( n − 1 ) ( 2 n − 2 + ( n − 2 ) 2 n − 3 ) =(n-1)(2^{n-2}+(n-2)2^{n-3}) =(n−1)(2n−2+(n−2)2n−3)
= ( n − 1 ) ( 2 n − 2 + n 2 n − 3 − 2 n − 2 ) =(n-1)(2^{n-2}+n2^{n-3}-2^{n-2}) =(n−1)(2n−2+n2n−3−2n−2)
= n ( n − 1 ) 2 n − 3 n(n-1)2^{n-3} n(n−1)2n−3
#include<bits/stdc++.h>
#define int ll
typedef long long ll;
using namespace std;
const int MOD = 99824353;
// a^k
int qmi(int a, int k) {
//注意k的取值范围,如果k能取到0,这行就要,如果取不到0,这行就不需要
// if (!k) return 0;//1^0 mod 1=0
int res = 1;
while (k) {
if (k & 1) res = res * a % MOD;
a = a * a % MOD;
k >>= 1;
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int ans = 0;
if (n == 1) ans = 0;
else if (n == 2) ans = 1;
else ans = ((n % MOD) * ((n - 1) % MOD)) % MOD * qmi(2, n - 3) % MOD;
cout << ans << endl;
return 0;
}
思路:
先看字符串a和b的长度,定义字符串长度长的为大串,字符串长度短的为小串。
① 判断小串是否是大串的子字符串,如果是则返回大串的长度
② 找出以字符串a为前缀,字符串b为后缀公共子串 l 1 l_1 l1,找出以字符串b为前缀,字符串a为后缀的公共子串 l 2 l_2 l2
比较公共子串的长度
ans = 字符串a长度+字符串b长度-max(公共子串 l 1 l_1 l1 长度,公共子串 l 2 l_2 l2 长度)
#include<bits/stdc++.h>
#define int ll
typedef long long ll;
using namespace std;
const int N = 1010;
string a, b;
bool eq(char a, char b) {
if (a == b || a == '?' || b == '?') return true;
else return false;
}
int mlen(string a, string b) {
int len = 10010;//最坏情况是10000,a和b拼起来
int lena = a.size(), lenb = b.size();
for (int i = 0; i < lena; i++) {
int f = 1;
for (int j = 0; j < lenb && i + j < lena; j++) {
if (!eq(a[i + j], b[j])) {
f = 0;
break;
}
}
if (f) len = min(len, max(i + lenb, lena));
}
return len;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> a >> b;
int lena = a.size(), lenb = b.size();
//最坏的情况,二者没有公共子串
int ans = lena + lenb;
ans = min(ans, min(mlen(a, b), mlen(b, a)));
cout << ans << endl;
return 0;
}
待更
f [ i ] [ j ] [ k ] : 表 示 a 有 i 元 , b 有 j 元 , c 有 k 元 时 , 他 们 请 客 的 方 案 数 f[i][j][k]:表示a有i元,b有j元,c有k元时,他们请客的方案数 f[i][j][k]:表示a有i元,b有j元,c有k元时,他们请客的方案数
通过观察:一人一次性买三个人的单,即每个人每次给的钱:300,450,750,且均是150的倍数,所以,可以做一个预处理,都 /150。
那么分别对应,2,3,5;
下面就一顿操作,纯朴素的三维DP做法。
#include<bits/stdc++.h>
#define int ll
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int N = 110;
int f[N][N][N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b, c;
cin >> a >> b >> c;
a /= 150;
b /= 150;
c /= 150;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 1; k++) {
f[i][j][k] = 1;
}
}
}
for (int i = 0; i <= a; i++) {
for (int j = 0; j <= b; j++) {
for (int k = 0; k <= c; k++) {
//300,450,750
if (i >= 2) f[i][j][k] = (f[i][j][k] + f[i - 2][j][k]) % MOD;
if (i >= 3) f[i][j][k] = (f[i][j][k] + f[i - 3][j][k]) % MOD;
if (i >= 5) f[i][j][k] = (f[i][j][k] + f[i - 5][j][k]) % MOD;
if (j >= 2) f[i][j][k] = (f[i][j][k] + f[i][j - 2][k]) % MOD;
if (j >= 3) f[i][j][k] = (f[i][j][k] + f[i][j - 3][k]) % MOD;
if (j >= 5) f[i][j][k] = (f[i][j][k] + f[i][j - 5][k]) % MOD;
if (k >= 2) f[i][j][k] = (f[i][j][k] + f[i][j][k - 2]) % MOD;
if (k >= 3) f[i][j][k] = (f[i][j][k] + f[i][j][k - 3]) % MOD;
if (k >= 5) f[i][j][k] = (f[i][j][k] + f[i][j][k - 5]) % MOD;
}
}
}
cout << f[a][b][c] % MOD << endl;
return 0;
}
待更
不会
文章浏览阅读2k次,点赞3次,收藏2次。打包aab的时候遇到一些神奇的问题:jarsigner.exefailed with exit code 1;Execution failed for task ':app:transformClassesWithDexBuilderForRelease'.;Cause: failed to decrypt safe contents entry: java.io.IOException: getSecretKey failed: Password is not ASCII_the android aab installation package error = = / lib/arm64 libpython. zip. s
文章浏览阅读7.5k次,点赞2次,收藏26次。Bootstrap在开发响应式移动页面方面是最流行的HTML,CSS,和JS框架。在官方网站上分别展示在CSS,Componts,还有JS的相关组件。本文详细介绍通过bootstrap框架制作一个精美的网页(内容方面参考慕课网的相关资料) 其中顶部页面的导航栏部分点击“特点”可以实现小标兰,点击“关于可以弹出介绍性的文字”图片可以实现滚动效果。最主要的功能是当页面缩放时,网页中所有的元素都能自适应_根据效果图,利用boostrap完成响应式页面的设计与实现
文章浏览阅读1k次。每年互联网总会有个新模式出现,从BBS,LBS,GROUP,O2O,再到现在的共享,大部分都是抄,对,就是一个抄,国外发展的不错,那就抄到国内,拿来主义嘛。 然后迅速找风投,狂补贴烧钱,反正不是自己的钱,随便砸了。 只有迅速抢占市场,跑马圈地,才能更多的融资。 做不了老大,可以做老二, 反正刷了存在感,号称有多少多少用户,就可以上市了! 上不市没关系,等合并! 没人一起合体也没关系,等收_共享村长经营模式
文章浏览阅读1k次。2012年微软做的最有诚意的一件事就是对HTML5的支持了:a) IE10对HTML5很好的支持,彻底洗刷了IE9稚嫩残缺的形象,绝大多数为Webkit优化的网页都可以完美的在IE10上运行,且性能非常的好,直接秒杀其他浏览器。做web应用,最担心的就是性能问题,特别是游戏类型的应用。在js性能被人四处诟病时,IE的表现给开发者打了一剂强心针。b) 把js提升到原生语言的地位,可以直接调用_ie10中.catch
文章浏览阅读360次。大纲:一、前言二、GitHub简介三、注册GitHub账号四、配置GitHub五、使用GitHub六、参与GitHub中其它开源项目七、总结注,GitHub官网:https://github.com/,客户端版本:gitversion 1.9.2.msysgit.0。所有软件请到这里下载:http://msysgit.github.io/。 一、前言在前面_github 使用 指导图
文章浏览阅读892次,点赞13次,收藏6次。邻接表(链式向前星)链式向前星:用来储存边的信息的以中方法。优点:速度快,节省空间,很常用如果我们用 Vector 来建边,相当于开的是一个动态的二维数组,较数组模拟来说比较慢。有时候还卡空间(被某一道题卡崩的YMF学长:我再用Vector建边我是_链式向前星的优点
文章浏览阅读2.6k次,点赞2次,收藏7次。目前已经是微信小程序的第二周学习,有很多知识点需要巩固、消化、记忆。js的计时器这个东西想必前端学者并不陌生,它在生产生活中也经常出现,也非常实用,今天在小程序里用它来做一个短信获取倒计时的功能、其中涉及到定时器的开启、暂停、继续html》其中设置了按钮的大小,按钮的样式和是否禁用采用数据绑定的形式来动态设置,绑定了js的事件,用来触发计时器。js》count用来动态调整倒计时数值,timerId用来当作计时器的id,因为我们要做继续计时器的功能,所以会跨函数调用计时器,直接将其设置为全_js 中计时器成功游戏后如何停止计时
文章浏览阅读362次。http://www.augsky.com/599.htmlhttp://blog.csdn.net/gaohuaid/article/details/38750283/http://www.111cn.net/sys/CentOS/63645.htm_centos7获取插入的u盘序列号
文章浏览阅读7.3k次,点赞21次,收藏68次。# (c) Silvaco Inc., 2018go atlas ## GaN LED Device Simulation## Blue single-quantum well LED## Parameter used for this blue SQW LED#############################################################..._silvaco能仿真量子阱
文章浏览阅读3.9k次,点赞4次,收藏42次。SLAM14讲汇总1、安装包及其所在位置:安装包:clion-2021.1.1、eigen-3.2.10、OpenCV、ORB_SLAM2、Pangolin、g2o、所在位置:/home/zhe/1/orb-slam和/home/zhe/Software学习记录:代码_深蓝学院课程合集百度网盘
文章浏览阅读4k次,点赞3次,收藏13次。摘要:采用命令行模式操控Linux系统非常重要。本文总结Linux常用的命令,包括命令的含义,命令的用法以及命令的拓展。关键词:命令行模式 Linux常用命令给Linux系统下达命令,即写Linux命令操控Linux系统做事情,是重要的手段之一。Linux的命令很多,不同类型或版本的Linux系统,Linux命令 在数量上和具体命令上会存在些许差异。但是,Linux常用命_linux 常用命令
文章浏览阅读1.2w次,点赞4次,收藏14次。添加以下内容到指定CSS文件,并引入项目即可生效/* 偶数行背景色 */.layui-table[lay-even] tr:nth-child(even) { /* background-color: #aaffaa; */ background-color: #eeffee;}/* 鼠标指向表格时,奇数行背景颜色 */.layui-table tbody tr:h..._layui table 背景色