https://ac.nowcoder.com/acm/contest/1099#question
emmm...10月8日...昨晚失眠....今天写写水题解。。。好垃圾啊。。。
关于这个题那个点分治明天一定学....
A-全1子矩阵 签到题 给一个n*m的矩阵 一开始全是0 之后把一个矩阵的元素全部设为1 给一个矩阵 判断是不是这样产生的矩阵
思路：输入的时候扫一遍 确定最小的x y（该点并非为1）同时确定最大的x y 之后根据之间的差计算之间1的数量 是否和样例给的1数量相等 但是不知道为什么根据这4个值扫一遍就WA....但是算数量就可以
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
const int maxn = 1e6 + 5;
char arr[15][15];
int main() {
ios::sync_with_stdio(0);
int n, m;
int sx, sy, ex, ey;
int cnt;
while (cin >> n >> m) {
sx = 100;
sy = 100;
ex = 0;
ey = 0;
cnt = 0;
for (int i = 0; i < n; i++) {//遍输入遍扫
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == '1') {
cnt++;
sx = min(sx, i);
sy = min(sy, j);
ex = max(i, ex);
ey = max(j, ey);
}
}
}
if (cnt != (ex - sx + 1) * (ey - sy + 1)) cout << "No\n";//互相比较数量看看是否相等
else cout << "Yes\n";
}
return 0;
}
B-组合数
思路：这个题 前面那部分就是组合数的公式 就是C(n,k) 先优化一个k 保证k是小的那一部分 然后化简为上k项下k项的一个式子 就是高中最常用的那个 然后算 中间就不会炸数 这里我重新敲一遍队长和他们队的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e3 + 5;
const int INF = 0x3f3f3f3f;
ll c[N][N];
void judge(int n, int &k) {
if(k > n / 2) k = n - k;
}
int main() {
int n, k;
while(~scanf("%d%d", &n, &k)) {
judge(n, k);
bool ok = false;
long double now = 1;
for(int i = 1; i <= k; i++) {
now *= n - i + 1;
now /= k - i + 1;
if(now > 1e18) {
printf("%0.f\n", 1e18);
ok = true;
break;
}
}
if(!ok) {
printf("%0.Lf\n", now);
}
}
}
E- Numbers
给定0-99个数字 给定一个字符串 每个数字用一次
有多少种组合方式
思路：DFS 具体看代码
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
const int maxn = 1e6 + 5;
string s;
int result = 0;
bool vis[100];
void dfs(int i) {//i 代表位数
if (i == s.size()) {//如果正好等于s的长度
result++;
}
else {
int a = s[i] - '0';//这一位当前数字
if (!vis[a]) {//没用过
vis[a] = 1;//用一下
dfs(i + 1);//继续D下一位
vis[a] = 0;//还原
}
if (a != 0 && i + 2 <= s.size()) {//这一位不等于0 并且 连续两位没有超过s的最长长度
int b = a * 10 + s[i + 1] - '0';//选定两位
if (!vis[b]) {//同理
vis[b] = 1;
dfs(i + 2);
vis[b] = 0;
}
}
}
}
int main() {
while (cin >> s) {
result = 0;
memset(vis, 0, sizeof(vis));
dfs(0);//从0填充开始DFS
printf("%d\n", result);
}
return 0;
}
F-4 Buttons
题意 一开始在0，0 之后可以向上下左右四个方向走
最多走abcd 步数 可以走0步 问能到达的所有格子的总数 分四个象限计算 为当前方向全走加上之间所有的点 具体见代码
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;
typedef long long ll;
int n, a[4];
int solve(int n, int a[4]) {
int result = 0;
for (int i = 0; i < 4; i++) {
int x = a[i];
int y = a[(i + 1) % 4];
result += (n * (n - 1LL) / 2 % MOD * x % MOD * y + 1LL*n * x) % MOD;
if (result >= MOD) {
result -= MOD;
}
}
return result+1;
}
int main() {
while (cin >> n) {
for (int i = 0; i < 4; i++) cin >> a[i];
printf("%d\n", solve(n, a));
}
return 0;
}
J-点分治 明天看看
Comments | NOTHING