A、
手摸不难发现,能做出的正方形大小就是当前的最大长度。所以直接输出向上取整即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int main(){
// freopen("hh.txt", "r", stdin);
int T; read(T);
while(T--){
ll n;
read(n);
cout << (n + 1) / 2 << endl;
}
return 0;
}
B
很烧的一道题。可以知道有意义的字串长度不超过 \(100\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int n;
char s[N];
int a[N];
int num[N][11];
int main(){
// freopen("hh.txt", "r", stdin);
int T; read(T);
while(T--){
read(n);
scanf("%s", s + 1);
for(int i = 1; i <= n; i++)
a[i] = s[i] - '0';
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 9; j++) num[i][j] = 0;
ll ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 9; j++)
num[i][j] = num[i-1][j];
num[i][a[i]]++;
}
for(int i = 1; i <= n; i++){
int tot = 0;
bitset <11> vis(0);
for(int j = i; j && j >= i - 99; j--){
if(!vis[a[j]]) tot++, vis[a[j]] = 1;
bool flag = 1;
for(int h = 0; h <= 9; h++){
int tmp = num[i][h] - num[j-1][h];
if(tmp > tot){
flag = 0;
break;
}
}
if(flag) ans++;
}
}
cout << ans << endl;
}
return 0;
}
C
这道题比赛的时候想复杂了,时间不够没码出来。
换个思路:根据 \(0\) 把原串划分成很多个区间。对于第一个区间,无法改变,所以扫一遍直接看有多少个前缀和为 \(0\) 即可。对于之后的每一个 \(0\),考虑其右边那一段(在两个 \(0\) 之间的那一段)有多少凸起,选择数量最大的那个削掉即可。
那么为什么不用考虑左侧多余的非 \(0\) 值呢?注意这里是前缀和,我们只要每次都把 \(0\) 上多减一个数将其前面的影响消掉就好了,不需要考虑具体减掉多少。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int n;
ll a[N];
int tot = 0;
ll sum[N];
map <ll, ll> G;
int main(){
// freopen("hh.txt", "r", stdin);
int T; read(T);
while(T--){
G.clear();
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
ll sum = 0;
ll ans = 0;
bool alr = 0;
ll maxn = 0;
for(int i = 1; i <= n; i++){
if(a[i] == 0){
if(alr) ans += maxn; // 区分第一段出来
else ans += G[0];
alr = 1;
G.clear();
maxn = 0;
}
sum += a[i];
G[sum]++;
maxn = max(maxn, G[sum]);
}
if(alr) ans += maxn; // 特判无 0 情况
else ans += G[0];
cout << ans << endl;
}
return 0;
}
原文地址:http://www.cnblogs.com/wondering-world/p/16885843.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性