A水题,但没开long long爆内存了......
H签到题 注意前导零,以及23:59:59后是00:00:00
I签到题,但最开始对题意理解有偏差,导致罚时太多.
#include<bits/stdc++.h>
using namespace std;
int main(){
double x, y, z, s, d1;
cin >> x >> y >> z >> s;
d1 = sqrt(x * x + y * y);
if(d1 >= z) cout << "No" << endl;
else if(s * 2.0 + d1 <= z) cout << "Yes" << endl;
else cout << "Possible" << endl;
return 0;
}
D题目描述:
f(x,y) = x * y + x + y;
给定H,求有多少个 (x, y) 使 f(x, y) = H 成立
x, y 无序
input:
第一行输入T, 表示有T组数据
接下来T行,每行输入一个数H
output:
输出T行, 每行一个数, 表示有多少个(x, y) 使 f(x, y) = H 成立
输入样例:
2
1
23
输出样例:
1
4
显然 H + 1 = (x + 1) * (y + 1)
所以即求H+1的<=sqrt(H+1)的因数个数
代码没提交过,应该能过吧...
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
int n;
while(t--){
scanf("%d",&n);
int cnt=0;
n++;
for(int i = sqrt(n); i >= 1; i--)
if(n % i == 0) cnt++;
printf("%d\n",cnt);
}
return 0;
}
K题目描述:
input:
第一行输入n, m, 表示给一个n * m的矩阵A
接下来n行, 每行m个数, 数值为0或1
output:
输出一个n * m矩阵B, Bij的值为Aij到最近的1需要走多少步
(只能上下左右,不能斜走,一步只有一个单位).
数据范围: n, m<=500
输入样例:
2 3
0 0 0
1 0 1
输出样例:
1 2 1
0 1 0
简单广搜吧 没什么难的
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int n, m;
int vis[510][510];
const int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
queue <P> q;
inline bool in(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main(){
scanf("%d%d", &n ,&m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &vis[i][j]);
if(vis[i][j]){
q.push(make_pair(i, j));
}
}
}
while(!q.empty()){
P u = q.front(); q.pop();
int x = u.first, y = u.second;
for(int i = 0; i < 4; i++){
int nx = x + dir[i][0], ny = y + dir[i][1];
if(in(nx, ny) && !vis[nx][ny]){
vis[nx][ny] = vis[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
printf("%d ", vis[i][j] - 1);
printf("\n");
}
return 0;
}
F
终于不是签到题了
题目描述:
有一种二进制数叫8-bits数,它的所有数字里有8个1.例如11111111, 11100011111, 1010101010101010......
给定一个n,求第n大的8-bits数.
input:
多组数据
每次输入一个数n
output:
输出第n大的8-bits数的十进制数
输入样例:
1
2
3
1000
输出样例:
255
383
447
7032
最开始我以为是数论的题,直接跳过,后来在队友提醒下发现原来是dp...
在结束前20minAC贼jb刺激
分两步:
第一步:求出这串数有多少个零
第二步:找到这些零的位置
dp[i][j]表示前i个数中有j个零的方案有多少种.注意首位数字是确定了的
(为什么不直接说为1呢,因为后面找零的位置时也用了该dp,但假设的首位数字为零).
详见代码
#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000], vis[1000];
//dp[i][j]表示前i个数中有j个零的方案有多少种.首位数字已确定.
int main(){
int n;
while(scanf("%d", &n)!= EOF){
int sum = 1, i;//sum为 1 是考虑11111111
memset(dp, 0, sizeof(dp));
memset(vis, 0, sizeof(vis));
for(i = 1; i <= 8; i++) dp[i][0] = 1;//首位数字为1
for(i = 1; ; i++){
if(sum >= n){//i - 1个零, 长度为i + 7
int delta = n - sum + dp[i + 7][i - 1];
//delta表示第n大的8-bits数在长度为i+7的8-bits数里是第delta大的数
int t = i + 7, j = i - 1;
/*
一共有t个数
还需确定j个零的位置
第一位数肯定为1, 判断第二位数能否为0
假设第二位数为零,则之后的长度t-2的数串中有j-1个零的方案数得大于delta
即dp[t-1] >=delta(首位数字假设为零
否则第二位数为1, delta自减dp[t-1](已有dp[t-1]种方案被判断
接着判断第三位数是否为零. 以此类推
*/
while(j){
if(delta <= dp[t - 1][j - 1]){
//零的位置等于总长度i+7减去待判断数串长度t-1再加1,即i-7-(t-1)+1=i+9-t
vis[i + 9 - t] = 1;//记录下0的位置
t--; j--;
}
else{
delta -= dp[t-1][j-1];
t--;
}
}
break;
}
for(int j = i; j <= i + 8; j++)
dp[j][i] = dp[j-1][i] + dp[j-1][i-1];
sum += dp[i + 8][i];
}
//转十进制
int loc = i + 7;
long long ans = 0, base = 1;
while(loc > 0){
ans += base * (1-vis[loc]);
loc--;
base *= 2;
}
cout << ans << endl;
}
return 0;
}
C
大佬说是博弈论的版题,只要写过就会.可我没见识过博弈论...溜
