就是给定两个数n和m,要求输出一个长宽为n和m的01矩阵,且要求横竖斜都不能有连续的三个数字相同。
直接构造就行,其实有很多种构造方法都满足题意,我这里直接以110为基础构造。(唯一一道过了的题)
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
const int N = 20 + 10;
const int mod = 1e9 + 7;
inline bool read(int &num) {
//quick read
char in;
bool IsN = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && (in < '0' || in > '9')) in = getchar();
if (in == '-') {
IsN = true;
num = 0;
} else num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
if (IsN) num = -num;
return true;
}
void solve() {
int n, m;
cin >> n >> m;
int out1 = 1, out2 = 1, cnt = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << out1;
out1 = (!out1);
}
out1 = out2;
cnt++;
if (cnt == 2){
cnt=0;
out2 = (!out2);
}
if (i != n)
cout << endl;
}
}
int main() {
solve();
return 0;
}
给定n个盒子,每个盒子里面有个球且是黑白中的一种。打开盒子有代价wi,且可以花费代价c获得剩下未开盒子的黑球数量,求获得所有盒子内球色的花费期望。
(一开始一看以为数学期望dp,想了半天发现没啥办法构造子问题)开盒子有两种策略,一种是全开不花那个c,还有就是花一次c再开部分盒子。花费c只可能花费一次,而且在数学表示上最开始花还是后面再花没区别,所以可以一开始就把c代价加上。花费c的最优贡献一定是剩下的盒子内全都是黑球,又知道对于下标i及之后的盒子,盒子内有白球的概率为(1-1/2^(n-i))(也就是全黑球的概率为1/2^(n-i),反过来就是存在白球的概率。又因为求的是期望,因此再乘个wi就完事了。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#define fo(ii, nn) for(int ii=1;ii<=nn;ii++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
const int N = 5000000 + 10;
const int mod = 1e9 + 7;
int n;
double c;
double w[N];
inline bool read(ll &num) {
//quick read
char in;
bool IsN = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && (in < '0' || in > '9')) in = getchar();
if (in == '-') {
IsN = true;
num = 0;
} else num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
if (IsN) num = -num;
return true;
}
int qp(int b, int p) {
int ans = 1;
int base = b, ansp = p;
for (; p; p >>= 1) {
if (p & 1) ans = (long long) ((ans * base));
base = (long long) ((base * base));
}
return ans;
}
void solve() {
double max1 = 0, max2 = 0, minans = 0;
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> w[i];
max1 += w[i];
}
sort(w + 1, w + n + 1);
double base = 1.0;
for (int i = n; i >= 1; i--) {
max2 += w[i] * (1.0 - base);
base /= 2.0;
}
max2 += c;
minans = min(max1, max2);
printf("%.6lf", minans);
}
int main() {
int t;
solve();
return 0;
}
给定一串n个数字的串,询问m次,每次询问给定一个k。求在数字串中有多少个不同的区间(l,r)满足区间极差>k(不等于),极差为最大值-最小值。
极差转换为单调队列维护区间最大值和最小值,遍历左端点l找符合条件的右边界下标数量,不断维护单调数组即可。另外实际操作的时候不需要真的找每一个右边界,只要找到第一个符合条件的右边界r后给答案加上n-r+1即可(因为当前的r如果已经满足了区间极差>k则右边界不管怎么向右移动都不影响这个极差值,且极差只会比之前的极差更大)。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#define fo(ii, nn) for(int ii=1;ii<=nn;ii++)
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pai;
const int N = 100000 + 10;
const int mod = 1e9 + 7;
int a[N];
int n;
int up[N], down[N];
inline bool read(int &num) {
//quick read
char in;
bool IsN = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && (in < '0' || in > '9')) in = getchar();
if (in == '-') {
IsN = true;
num = 0;
} else num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
if (IsN) num = -num;
return true;
}
void query(int k) {
ll ans = 0;
int h1 = 1, t1 = 0, h2 = 1, t2 = 0; // 1是递增单调队列,2是递减单调队列,队列头先+1用于避免头=尾时的数量判断错误
for (int l = 1, r = 1; r <= n; r++) {
while (h1 <= t1 && a[up[t1]] >= a[r]) t1--; // 前移队尾直到找到可插入ar的位置
up[++t1] = r;
while (h2 <= t2 && a[down[t2]] <= a[r]) t2--; // 同理
down[++t2] = r;
while (a[down[h2]] - a[up[h1]] > k) {
ans += 1ll * (n - r + 1); // r后面的区间都满足,因为最大值如何改变都绝对>k
l++;
while (l > up[h1]) h1++; // 右移l
while (l > down[h2]) h2++;
}
}
cout << ans << endl;
}
void solve() {
int m;
read(n);
read(m);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
fo(i, m) {
int x;
read(x);
query(x); // 查询
}
}
int main() {
int t;
solve();
return 0;
}