“强智杯“2020年湖南省大学生计算机程序设计竞赛——ABDGHI
oj: 链接A.2020oj: 链接题解直接暴力维护即可。代码#include <bits/stdc++.h>#define PI atan(1.0)*4#define rp(i,s,t) for ( int i = (s); i <= (t); i++)#define RP(i,t,s) for ( int i = (t); i >= (s); i--)#define s
·
oj: 链接
A.2020
oj: 链接
题解
直接暴力维护即可。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for ( int i = (s); i <= (t); i++)
#define RP(i,t,s) for ( int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
void solve(){
int n;
while(cin>>n){
string s;cin>>s;
int ans=0;
rp(i,0,n-1){
if(i+3<=n-1&&s[i]=='2'&&s[i+1]=='0'&&s[i+2]=='2'&&s[i+3]=='0'){
i=i+3;
ans++;
}
// outval2(i,ans);
}
cout<<ans<<endl;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}
B.2020 vs 2018
oj: 链接
题解
观察在 2018 2018 2018和 2020 2020 2020的图像可以发现，
最明显的区别在于 2018 2018 2018多了一个 1 1 1。
因此我们直接暴力枚举是否有 1 1 1即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int debug = 0;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while(ch < '0' || ch > '9') {
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct poi {
};
int n, m;
char s[57][57];
void init() {
_rep(i,1,n) scanf("%s",s[i]+1);
_rep(i,1,n){
dg outval(i);
_rep(j,i,n){
dg outval(j);
_rep(k,1,m){
int f=1;
if(i>1&&s[i-1][k]=='o') continue;
if(j<n&&s[j+1][k]=='o') continue;
_rep(l,i,j){
if(s[l][k]!='o'){
f=0;
break;
}
if(k>1){
if(s[l][k-1]=='o'){
f=0;
break;
}
}
if(k<m){
if(s[l][k+1]=='o'){
f=0;
break;
}
}
}
if(f){
puts("2018");
return ;
}
}
}
}
_rep(i,1,m){
_rep(j,i,m){
_rep(k,1,n){
int f=1;
if(i>1&&s[k][i-1]=='o') continue;
if(j<m&&s[k][j+1]=='o') continue;
_rep(l,i,j){
if(s[k][l]!='o'){
f=0;
break;
}
if(k>1){
if(s[k-1][l]=='o'){
f=0;
break;
}
}
if(k<n){
if(s[k+1][l]=='o'){
f=0;
break;
}
}
}
if(f){
puts("2018");
return ;
}
}
}
}
puts("2020");
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// debug = 1;
#endif
while(~scanf("%d%d",&n,&m)) init();
return 0;
}
D.String Commutativity
oj: 链接
题解
如果两个串有相同的最短循环节，则这两个串符合题目要求。用kmp求最短循环节，但kmp求出的最短循环节不一定符合题意，例如aba的最短循环节为ab，而kmp求出的为aba，所以应排除这种情况。即用m%x!=0判断是否最后一个循环节是否完全循环
代码
#include <cstring>
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn=1e6+7;
const int INF=0x3f3f3f3f;
#define M 50015
int next1[maxn];
char str[maxn],mo[maxn];
int ans;
map<string,int> mp;
string tran(int x){
string a;
for(int i=0;i<x;i++){
a.push_back(mo[i]);
}
return a;
}
void getnext()
{
int i=0,j=-1,m=strlen(mo);
while(i<m){
if(j==-1||mo[i]==mo[j])
next1[++i]=++j;
else
j=next1[j];
}
}
int main()
{
int t;
while(~scanf("%d",&t)){
mp.clear();
long long sum=0;
while(t--){
ans=0;
scanf("%s",mo);
next1[0]=-1;
getnext();
int m=strlen(mo);
int x=m-next1[m];
if(x<m&&m%x!=0){
x=m;
}
//printf("x:%d\n", x);
string y=tran(x);
mp[y]++;
}
map<string,int>::iterator it;
it=mp.begin();
while(it!=mp.end()){
int n=it->second;
sum+=1LL*n*(n-1)/2;
it++;
}
printf("%lld\n",sum);
}
return 0;
}
G.奇矩阵
oj: 链接
题解
可以直接暴力枚举过，时间复杂度: O ( n 2 ) O(n^{2}) O(n2)。
O ( n ) O(n) O(n)的做法：
先说结论
记录每一行数的和的奇偶性，
如果奇数的次数是否大于 1 1 1且偶数的次数大于 1 1 1肯定不是奇矩阵，否则是。
证明如下：
假设当前有 m m m列数，取两行数分别为：
x 1 , x 2 , . . . , x m x_{1},x_{2},...,x_{m} x1,x2,...,xm。
y 1 , y 2 , . . . , y m y_{1},y_{2},...,y_{m} y1,y2,...,ym。
令 d 1 = x 1 − y 1 d_{1}=x_{1}-y_{1} d1=x1−y1，
d 2 = x 2 − y 2 d_{2}=x_{2}-y_{2} d2=x2−y2，
d 3 = x 3 − y 3 d_{3}=x_{3}-y_{3} d3=x3−y3，
…
d m = x m − y m d_{m}=x_{m}-y_{m} dm=xm−ym
假设两行数的和都为偶数，那么可以得到
( d 1 + d 2 + . . . + d m ) (d_{1}+d_{2}+...+d_{m}) (d1+d2+...+dm)% 2 = 0 2=0 2=0。
因为题目给的是绝对值求和，
如果当前差值是 d i d_{i} di，
如果 d i d_{i} di为正数没有影响，
如果 d i d_{i} di为负数的话对答案的影响是加上 2 × ∣ d i ∣ 2\times |d_{i}| 2×∣di∣。
那么可以发现 ( d 1 + d 2 + . . . + d m + 2 × ∣ d i ∣ ) (d_{1}+d_{2}+...+d_{m}+2\times |d_{i}|) (d1+d2+...+dm+2×∣di∣)% 2 = 0 2=0 2=0，即对答案的奇偶性没有影响。
因此结论得证。
代码
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int debug = 0;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while(ch < '0' || ch > '9') {
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct poi {
};
int n, m;
int num[2];
void init() {
num[0] = num[1] = 0;
}
int sol() {
init();
_for(i, n) {
LL sum = 0;
_for(j, m) sum += read();
++num[sum & 1];
}
if(num[0] > 1 || num[1] > 1) return 0;
return 1;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
debug = 1;
#endif
while(cin>>n>>m) {
printf("%s\n", sol() ? "Yes":"No");
}
return 0;
}
H.矩阵并
oj: 链接
题解
分情况容斥一下即可求出答案。
参考下图
代码
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1005;
const LL mod = 1000000007;
int debug = 0;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct poi {
};
LL a, b;
void exgcd(LL a, LL b, LL &g, LL &x, LL &y) {
if (!b) {
g = a;
x = 1;
y = 0;
} else {
exgcd(b, a % b, g, y, x);
y -= x * (a / b);
}
}
LL inv(LL x, LL mod) {
LL a, k, g;
exgcd(x, mod, g, a, k);
if(a < 0) a += mod;
return a;
}
LL getval(LL a, LL b) {
LL ans = 0;
ans += a * a % mod * b % mod * b;
ans += a * b % mod * b % mod;
ans += a * a % mod * b % mod;
ans += a * b % mod;
ans %= mod;
ans *= inv(4, mod);
return ans % mod;
}
int sol() {
LL x = read(), xx = read(), y = read(), yy = read();
LL ans = 0;
ans += getval(a, b);
dg printf("累积：%lld\n", getval(a, b));
LL w1 = max(0LL, min(b, yy) - y);
LL box1 = w1 * (w1 + 1) % mod * inv(2, mod) % mod * max(0LL, a - xx) % mod * (xx - x) % mod;
LL w2 = max(0LL, min(a, xx) - x);
if(a < x) w2 = 0;
dg printf("w1:%lld\tw2:%lld\n", w1, w2);
LL box2 = w2 * (w2 + 1) % mod * inv(2, mod) % mod * max(0LL, b - yy) % mod * (yy - y) % mod;
LL box3 = max(0LL, a - xx) * max(0LL, b - yy) % mod * (xx - x) % mod * (yy - y) % mod;
LL ans2 = box1 + box2 + box3 + getval(max(0LL, min(a, xx) - x), max(0LL, min(b, yy) - y)); ans2 %= mod;
dg printf("box1:%lld\tbox2:%lld\tbox3:%lld\n", box1, box2, box3);
dg printf("减去：%lld\n", ans2);
ans += mod - ans2;
LL ans3 = (xx - x) * (yy - y) % mod * a % mod * b % mod;
ans += ans3;
dg printf("额外：%lld\n", ans3);
ans %= mod;
printf("%lld\n", ans);
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// debug = 1;
#endif
while(~scanf("%lld%lld", &a, &b)) {
sol();
}
return 0;
}
I.共线点
oj: 链接
题解
首先把三个线段按照高度排序，
然后用最高的线段的左端点和最低的线段的左端点连接成一条直线，
求出这个直线方程，把中间线段的 y y y值带入，这样求出的是有效区间的左端点。
同理可以得到有效区间的右端点。
判断一下中间线段是否和这个有效区间是否有交点即可。
求端点可以利用两点式快速求出来。
代码
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a) for(int i = 0, len = a; i < len; ++i)
#define _rep(i, a, b) for(int i = a, len = b; i <= len; ++i)
#define outval(a) cout << "debuging|" << #a << ":" << a << "\n";
#define dg if(debug)
typedef long long LL;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1005;
int debug = 0;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while(ch < '0' || ch > '9') {
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct poi {
int a, b, y;
bool operator<(const poi &b) const {
if(y != b.y) return y < b.y;
else if(a != b.a) return a < b.a;
else return this->b < b.b;
}
};
poi a[3];
void init() {
}
int sol() {
_rep(i, 1, 2) {
int aa, bb, yy;
scanf("%d%d%d", &aa, &bb, &yy);
a[i] = {aa, bb, yy};
}
sort(a, a + 3);
double x1 = 1.0 * (a[2].a - a[0].a) / (a[2].y - a[0].y) * (a[1].y - a[0].y) + a[0].a;
double x2 = 1.0 * (a[2].b - a[0].b) / (a[2].y - a[0].y) * (a[1].y - a[0].y) + a[0].b;
dg printf("xx1:%.2f\txx2:%.2f\n", x1, x2);
if(x1 - eps <= a[1].b && x2 + eps >= a[1].a) return 1;
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
debug = 1;
#endif
int aa, bb, yy;
while(~scanf("%d%d%d", &aa, &bb, &yy)) {
a[0] = {aa, bb, yy};
printf("%s\n", sol () ?"Yes":"No");
}
return 0;
}
惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)