奥门巴黎人手机网址【app】

程序员进级之算法练习(七十五)

2020-01-08 12:40·澳门巴黎人彩票

总结

在此以前运用的是QQ群分享,二零一五年想尝尝下新的享用形式,接待帮忙。

直播课程

主题材料大体

概念在笛卡尔坐标系中的生机勃勃棵树:全数的节点都在分歧的整点坐标上,全数的边都不重叠地平行于坐标轴上且边不足交叉。给定生龙活虎棵n\((n \leq 30)\卡塔尔个节点树,问它是不是能转化成笛Carl坐标系中的树。假若能则交由全体一些的坐标,必需满意\(x_i,y_i \leq 10^{18}\)

题解:只怕是看出最水的四个E...分开总括a和b,a组的数值固定,由于加减相互交错,每趟只需求加叁次改良的值只怕不加。全数望的b组数值存贰个set,每便在set二分查找和a差值最小的b,做差得到相对值最小值。

 

前言

品类进程越来越紧,留给自个儿的业余时间也更少。本次的题目仍来自于平时练手之作,标题1、2、3较为便于,4、5有一些难度。

Code

代码注释:
\(f[i][j][k]\)为字母 class="math inline">\(k\)出现在 class="math inline">\((i,j)\卡塔尔的次数的前缀和,程序中率先用二维差分管理了间距加法和单点求值,然后求前缀和重作冯妇了数组,然后再贰遍求前缀和兑现区间查询。
\(num[i][j]\)为点 class="math inline">\((i,j)\卡塔尔(قطر‎被操作矩阵的字符覆盖的次数
\(g[i][j]\State of Qatar为原体系 class="math inline">\((i,j)\卡塔尔国和别的具备操作矩阵间隔和,程序中求了前缀和.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
const int maxn = 1024;
const int maxm = 300010;
ll s[maxn][maxn],num[maxn][maxn];
ll g[maxn][maxn];
ll f[maxn][maxn][28];

struct Node{
    ll x1,y1,x2,y2;
    int ch;
}a[maxm];
ll sum = 0;
int main(){
    int n,m,q;read(n);read(m);read(q);
    char ch;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            while(ch=getchar(),ch<'!');
            s[i][j] = ch - 'a';
        }
    }
    for(int i=1;i<=q;++i){
        read(a[i].x1);read(a[i].y1);
        read(a[i].x2);read(a[i].y2);
        while(ch=getchar(),ch<'!');
        a[i].ch = ch - 'a';
        f[a[i].x1][a[i].y1][a[i].ch]++;
        f[a[i].x2+1][a[i].y1][a[i].ch]--;
        f[a[i].x1][a[i].y2+1][a[i].ch]--;
        f[a[i].x2+1][a[i].y2+1][a[i].ch]++;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<26;++k){
                f[i][j][k] += f[i-1][j][k] + f[i][j-1][k] - f[i-1][j-1][k];
                num[i][j] += f[i][j][k];
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            f[i][j][s[i][j]] += q - num[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<26;++k){
                g[i][j] += f[i][j][k]*abs(s[i][j] - k);
            }sum += g[i][j];
        }
    }
    //printf("%lld\n",sum);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<26;++k){
                f[i][j][k] += f[i-1][j][k] + f[i][j-1][k] - f[i-1][j-1][k];
            }g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
        }
    }
    ll ans = 1LL<<60;
    for(int i=1;i<=q;++i){
        ll nw = sum;
        for(int k=0;k<26;++k){
            nw += abs(k - a[i].ch)*(f[a[i].x2][a[i].y2][k] - f[a[i].x1-1][a[i].y2][k] - f[a[i].x2][a[i].y1-1][k] + f[a[i].x1-1][a[i].y1-1][k]);
        }nw -= (g[a[i].x2][a[i].y2] - g[a[i].x1-1][a[i].y2] - g[a[i].x2][a[i].y1-1] + g[a[i].x1-1][a[i].y1-1]);
        ans = min(ans,nw);
    }printf("%I64d",ans);
    getchar();getchar();
    return 0;
}

For the first example before any updates it's optimal to choose j = 0, f(0) = |(1 - 1) - (2 - 2) + (3 - 3) - (4 - 4) + (5 - 5)| = |0| = 0.

John将来根据卫星照片上的的这么些"#"块的形象来剖断什么是牛群,哪些是房间.假如三个"#"块形状的边是程度或垂直的矩形,则是房间.别的的则以为都以牛群.在首先个图中,有八个房子( 2x1, 2x5, and 1x1卡塔尔国和2群牛.

正文

标题链接题目轮廓:Mahmoud和Ehab在玩二个数字游戏。有贰个平头n,从Mahmoud开首,轮换选取贰个数字a,供给:

  • 1 <= a <= n;
  • 如假诺Mahmoud采取,a必得是偶数;借使是Ehab选取,a必需是奇数。

选完数字之后,n=n-a; 无法选则输掉游戏。尽管五个人的表决都很周密, 今后提交数字n,请问何人能赢。

输入数据:n (1 ≤ n ≤ 1e9)

Examplesinput1outputEhabinput2outputMahmoud

难点分析:n=1时,Mahmoud必输;n=2时,Mahmoud必胜;n=奇数时,因为Mahmoud只好取偶数,取完现在依然奇数,那么Ehab直接取n就能够;n=偶数时,因为Mahmoud只好取偶数,那么间接取n就必胜。

 lld n; cin >> n; cout << (n % 2 ? "Ehab" : "Mahmoud") << endl;

主题素材链接主题材料大要:有n个地点,还或者有a个班级1的上学的儿童,b个班级2的学习者;n个地点排成生龙活虎行,由后生可畏行长度为n的字符串表示,*代表曾经有人,.表示可以坐人;以往不期望班级1和班级2的上学的小孩子坐在相邻的岗位,问最多能布署几人坐下。

输入数据:n , a and b ( 1 ≤ n ≤ 2 ⋅ 10 5 , 0 ≤ a , b ≤ 2 ⋅ 10 5 , a

  • b > 0 )

Examplesinput5 1 1*...*output2input6 2 3*...*.output4

主题材料深入深入分析:多少个简易的战略:对于有空位的,优先选项人数相当少的班级;其次,纵然上一个地方坐了班级1的上学的儿童,则这一个职分做班级2;

难题链接难题概略:n个字符串,长度均为m;今后要从n个字符串中,各类选出贰个字符,组成叁个尺寸为n密码,要求:包蕴数字、小写字母、特殊字符('#','*','&'中的多个);

今天豆蔻年华旦选拔字符的光标停在各样字符的最左侧,每回能够左移或许右移操作,借使在最侧边左移会变到最侧边,在最左边右移会变到最左侧;问,至少须求操作几回,技术选出一个官方的密码?(数据保险,必然存在法定的密码)

输入数据:n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50)

Examplesinput3 4``1\*\*2``a3*0``c4\*\*output1样例解释:选中的密码是1a*,仅需把第三行的c移动到最右面;

主题素材解析:标题标必要是选出合法的密码,那么最多移动四个光标;现在的精选是活动哪些光标,使得次数起码;先看暴力的事态:从肆二十个选项3个的排列是50*49*48,每一遍枚举的复杂度是m*2;总的复杂度是O;是实用的方案。

思考🤔:另少年老成种解法:每行有七种接收,不动,移动到小写字母,移动到数字,移动到特殊字符;那么能够用dp[i][j] 来表示前i行,密码已满意状态为j的相当的小光标移动间隔;j ∈ [0, 1 << 3],用二进制来代表景况j;每行有七个转移方程,复杂度为O;总体的复杂度是O;

难题链接

难题大体:假诺有三个数组a,数组b,长度都为n,並且l ≤ a[i] ≤ r 和 l ≤ b[i] ≤ r;定义多个数组c,c[i] = b[i] - a[i],而且数组c里面未有同样的因素;数组p 表示数组c中的大小关系,比如说 c=[250, 200, 300, 100, 50], 那么 p = [4, 3, 5, 2, 1];

现行反革命给出数组a和p,还大概有长度n,数组b的约束[l, r];求是还是不是存在二个数组b,满足须要?倘使有,输出数组b;若无,输出-1;

输入数据:n, l, r (1 ≤ n ≤ 1e5, 1 ≤ l ≤ r ≤ 1e9)(l ≤ a[i] ≤ r)(1 ≤ p[i] ≤ n)

Examplesinput5 1 51 1 1 1 13 1 5 4 2output3 1 5 4 2

标题深入深入分析:依靠难点定义,大家必要在[l, r]限定内,搜索四个数组b,满意c[i]=b[i] - a[i], c[i]各差别,并且大小顺序满足数组p;轻巧了然,b[i] = a[i] + c[i];c[i]是不显著的,因为明确c[i]就一定于规定b[i];节制在于b[i]有范围,否则c[i]只需在[1, n]按梯次采纳就能够;

那正是说我们可以还是不可以先依据c=[1, n],直接算出b[i]的范围,再对b[i]的值实行减少?先对p排序,得到[1,2,3]的数组,和新的a[i];那么有b[i]=a[i]+i;也许会有 b[i]<l || b[i]>r 的情形现身。假如找到四个十分的小值bMin, 二个最大值bMax;现在供给保险最小值bMin>=l, 那么全体数组b,都应当+的高低;(这里思忖樂,是或不是存在不合并加的更优解?bMin的值变大,招致其相应的c[j]变大, c[1j]能够不改变,c[j+1n]的值会变大)

因而采纳,c[i]实时总计,假若b[i]<l ,那么直接令b[i]=l, 那么c= b[i] - a[i],b[i]变大会引致c[i],变大。只要保障以往b[i] <= r即可;

题目链接主题材料大要:有风度翩翩棵n个点的树,已知n个点之间的不断关系,将来供给把树的节点放到叁个二维坐标轴上务求边和x/y轴平行,边未有重叠;

科技世界 1

输入数据:输入,第一行n接下来n-1行,分别是ui 和 vi,表示 点ui和vi相连,ui, vi (1 ≤ ui, vi ≤ n)

出口, 假如无解,输出NO;倘使有解,先输出YES,接下去n行,分别输入n个点的坐标何况坐标[xi, yi] 满足 (|xi|, |yi| ≤ 1e18)

n (1 ≤ n ≤ 30)xi, yi (|xi|, |yi| ≤ 1e18)

Examplesinput71 21 32 42 53 63 7outputYES0 01 00 12 01 -1-1 10 2

主题材料解析:轻便通晓,如若某个点的边超越5个,那么早晚是无解。其余情况下,因为给出的xi,yi的界定不小,分明是有解的。先假一定1为root,别的点为子节点,来考查问题的trick所在:1、子节点中的数目不定,不佳分配具体的前后相继顺序;2、要防止两个子节点直接相互影响交错;3、防止多子节点与到事情发生前的父节点的边存在交错;

意气风发旦从叶子节点到根节点的分红坐标,叶子节点的坐标分配必要通晓父节点的坐标;那么我们得以先假定父节点的坐标为,子节点的坐标就在的底蕴上海展览中心开调度;沿着这么些思路,大家供给保障子节点的坐标和父节点的坐标保持一定的间隔;阅览到点独有三十多少个,给出的限量相当的大,大家得以接收每一遍给节点分配2^i的偏离:那样保险四个子节点不会交错,何况不会与父节点交错;(因为2^0

  • 2^1 + ... + 2^i < 2^i+1;最大的点坐标为2^31 - 1,在客观限制内。故而,是生机勃勃种客观的解法。

题解

好费劲啊那题。。真钦佩在竞赛中做出来的神犇们...
率先大家尝试枚举所求矩阵.
如今即使我们能在\(< O(n)\State of Qatar的日子内求出答案就可以.
这也能做?你是不是来搞笑的!
我们开掘,这个时候咱们得以再枚举风华正茂边全数的其余矩阵,挨个求间隔
不过大家有五个属性尚未动用

  • 某七个范围内的有着字符全部平等
  • 另意气风发局地的字符完全部是开端矩阵的字符

怎么选用那么些性质呢?
笔者们能够想到分别管理出贰十六个阿拉伯语字母在全数操作发生的矩形内相配时对相差总和做出的贡献
那样能够使用前缀和的措施O(26卡塔尔(قطر‎总结第一条性质中揭橥的范围
而是大家预处理进献时,算进献应该和别的具有的操作爆发的矩阵相称
据此大家还相应预管理出在颇有操作发生的的矩阵中某一个字母出今后某一点的次数
下一场做前缀和也能够做到O(26State of Qatar查询。
下一场大家在管理出初叶矩阵在装有操作发生的矩阵中的间隔之和。

进行查询的时候,大家也必要减去大家眼下枚举的操作矩阵对方才的预管理值做出的孝敬。

256 megabytes

* 和 2..Highlander+1行: 第 i+1 行表示照片的第 i 长势况,由 C 字符组成.

题解

判断abs(n,m) <= 1即可,注意n,m均为0的情况.

After the second update a becomes {2, 2, 3, 4, 5} and it's optimal to choose j = 1, f(1) = |(2 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |0| = 0.

数量范围

Problem E

0
9
0
0

大家有三个N位数字的电子钟,当岁月达到10^N-1时,下黄金年代秒就归0。上边我们提交数字0 到 9的比葫芦画瓢图。

Problem D

time limit per test

四题就比较麻烦了,模拟赛上自家一直屏弃。

主题素材大体

有三数组\(a,b,c\)有\(c_i = b_i - a_i\)满足\(c_i\卡塔尔互不相近,且\(a_i,b_i \in [l,r]\卡塔尔(قطر‎.今后给定数组\(a\卡塔尔和离散化后的\(c\State of Qatar,还原出放肆二个立见成效的\(b\卡塔尔国数组.无解输出-1.
\(n \leq 10^5\)

Example

输入

1

.PPPPKP.

........

........

........

........

........

........

........

2

P......P

........

........

........

...KK...

........

........

P......P

.....P.P

..K....P

....K...

..PP...P

...K..KK

........

K.......

KP.K....

输出

6

20

9

problem A

The first line should contain the minimum value of the function f before any update.

设初步状态为O奥迪Q5I,f[i,j]记录i个数能不能够用j个灯管构成。

标题大要

已知有n个偶数,m个奇数,问那些数有未有非常大希望构成三个严俊递增1的行列

Then q lines follow describing the queries. Each of them contains three integers l**i r**i x**i (1 ≤ l**i ≤ r**i ≤ n,  - 109 ≤ x ≤ 109) — range to be updated and added value.

此题的思维方式是:

标题轮廓

给定八个\(n*m\State of Qatar的开头字符矩阵,有\(q\State of Qatar次操作,每一趟操作在起头矩阵上把\((a_i,b_i)\)到\((c_i,d_i)\卡塔尔之间的兼具字符全部蒙面为\(c_i\卡塔尔国。两字符的距离定义为\(|ch_1-ch_2|\卡塔尔国,矩阵的间距定义为对应字符间距之和。在有着操作产生的队列中取一个队列,使那么些行列和其它类别的相距的总的数量最小。
\(n,m \leq 10^3 ; q \leq 3*10^5\)

题目:

每黄金时代组有8行,每行8个字符。字符唯有'.',大写'P',大写'K'三种字符。'P'和'K'的个数范围都在[1,10]。

无须吟唱,直接传送

The third line contains m integers b1, b2, ..., b**m. ( - 109 ≤ b**i ≤ 109) — elements of b.

倘诺 ( seth xor setj 卡塔尔(قطر‎+seth=setj 那么 seth 正是 setj 的子集结。评释略(其实本人也不精通怎么注解,想到的应当是对的))

题解:

读了半天没读懂题,见到样例解释才明白。

我们开掘大家只用留意那三种东西的留存就能够
而各类字符串中独有三个指针,也便是每种字符串中不能不选取三个字符
就此最少选择3个字符串
那正是说大家\(O(n^3)\卡塔尔枚举是哪八个字符串,并且每一种字符串的指针应该本着什么

之所以我们直接预管理一下种种字符串中针对各类字符的渺小移动次数就能够

E. Mahmoud and Ehab and the function

.#..

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 64;
int G[maxn][11],fa[maxn];
ll x[maxn],y[maxn];
int dx[] = {0,1,-1,0,0};
int dy[] = {0,0,0,1,-1};
inline int indx(int i){
    if(i == 1) return 2;
    if(i == 2) return 1;
    if(i == 3) return 4;
    if(i == 4) return 3;
}
void dfs(int u,ll d,int k){
    for(int i=1;i<=G[u][0] && k;++i){
        if(G[u][i] == fa[u]) swap(G[u][i],G[u][indx(k)]);
    }
    for(int i=1;i<=G[u][0];++i){
        if(G[u][i] == fa[u]) continue;
        x[G[u][i]] = x[u] + d*dx[i];
        y[G[u][i]] = y[u] + d*dy[i];
        fa[G[u][i]] = u;
        dfs(G[u][i],d>>1,i);
    }
}
int main(){
    int n;read(n);
    for(int i=1,u,v;i<n;++i){
        read(u);read(v);
        G[u][++G[u][0]] = v;if(G[u][0] == 5) return puts("NO");
        G[v][++G[v][0]] = u;if(G[v][0] == 5) return puts("NO");
    }
    x[1] = y[1] = 0;fa[1] = 1;
    dfs(1,1LL<<58,0);puts("YES");
    for(int i=1;i<=n;++i) printf("%lld %lld\n",x[i],y[i]);
    getchar();getchar();
    return 0;
}

Please help Mahmoud and Ehab.

先来看K与P人数都在[1..10] 之间。考虑搜索或DP。

Problem F

standard output

输出:DigitalCounter.out

题解

我们有\(c_i = b_i - a_i\)所以\(b_i = a_i + c_i\)
据此大家总括出\(b\)数组,再根据\(l\卡塔尔(قطر‎的上面界调度,判定上面界是不是超越就能够

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 100010;
int a[maxn],b[maxn],c[maxn];
int main(){
    int n,l,r;read(n);read(l);read(r);
    for(int i=1;i<=n;++i) read(a[i]);
    int maxx = -0x3f3f3f3f,minn = 0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        read(c[i]);
        b[i] = a[i] + c[i];
        minn = cat_min(minn,b[i]);
        maxx = cat_max(maxx,b[i]);
    }
    if(maxx - minn > r - l) return puts("-1");
    int x = minn - l;
    for(int i=1;i<=n;++i){
        b[i] -= x;
        printf("%d",b[i]);
        if(i != n) putchar(' ');
        else putchar('\n');
    }
    getchar();getchar();
    return 0;
}

input

输出:

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
int main(){
    int a,b;read(a);read(b);
    printf(abs(a-b) <= 1 && !(a == 0 && b == 0) ?  "YES" : "NO");
    getchar();getchar();
    return 0;
}

2 seconds

 

题解

很分明,各样节点的度数不能超越4.
咱俩得以表明在坐标域为\([-10^{18},10^{18}]\卡塔尔(قطر‎时风流倜傥旦满足度数要求,一定期存款在可行解。
很举世瞩目:现在最关键的是节点之间的直接冲突使得组织退步。
(假若您懂围棋的话,能够把现身冲突时的这种造型叫做愚形)
为此大家把节点之间的区间拉到丰裕大,使其不容许对相互爆发耳闻则诵。
因而大家社团的前七个点的间隔拉到\(2^{58}\)即可
接下来每一分布局下一个点的时候把间隔变为原本的二分之一
科技世界,那般纵然中间再装下剩下的贰十几个点也不会相互发生影响
如此那般布局就可以

The second line contains n integers a1, a2, ..., a**n. ( - 109 ≤ a**i ≤ 109) — elements of a.

应用结构法生成全体应用相通数量灯管的结果,寻觅最小就可以,当然要剪枝。

Problem C

  1 #define _CRT_SECURE_NO_DEPRECATE
  2 #pragma comment(linker, "/STACK:102400000,102400000")
  3 #include<iostream>  
  4 #include<cstdio>  
  5 #include<fstream>  
  6 #include<iomanip>
  7 #include<algorithm>  
  8 #include<cmath>  
  9 #include<deque>  
 10 #include<vector>
 11 #include<bitset>
 12 #include<queue>  
 13 #include<string>  
 14 #include<cstring>  
 15 #include<map>  
 16 #include<stack>  
 17 #include<set>
 18 #include<functional>
 19 #define pii pair<int, int>
 20 #define mod 1000000007
 21 #define mp make_pair
 22 #define pi acos(-1)
 23 #define eps 0.00000001
 24 #define mst(a,i) memset(a,i,sizeof(a))
 25 #define all(n) n.begin(),n.end()
 26 #define lson(x) ((x<<1))  
 27 #define rson(x) ((x<<1)|1) 
 28 #define inf 0x3f3f3f3f
 29 typedef long long ll;
 30 typedef unsigned long long ull;
 31 using namespace std;
 32 const int maxn = 1e5 + 5;
 33 set<ll>b;
 34 ll orib[maxn];
 35 
 36 void getbest(ll suma)
 37 {
 38     auto it = b.lower_bound(suma);
 39     ll best;
 40     if (it != b.end())
 41     {
 42         best = abs(suma - *it);
 43         if (it != b.begin())
 44         {
 45             it--;
 46             best = min(best, abs(suma - *it));
 47         }
 48     }
 49     else
 50     {
 51         it--;
 52         best = abs(suma - *it);
 53     }
 54     cout << best << endl;
 55     return;
 56 }
 57 
 58 int main()
 59 {
 60     ios::sync_with_stdio(false);
 61     cin.tie(0); cout.tie(0);
 62     int i, j,  m, n, q;
 63     cin >> n >> m >> q;
 64     ll suma = 0;
 65     ll flag = 1, k;
 66     for (int i = 1; i <= n; ++i)
 67     {
 68         cin >> k;
 69         suma += k*flag;
 70         flag *= -1;
 71     }
 72     for (int i = 1; i <= m; ++i)
 73         cin >> orib[i];
 74     ll sumb = 0;
 75     flag = 1;
 76     for (int i = 1; i <= n; ++i)
 77     {
 78         sumb += orib[i] * flag;
 79         flag *= -1;
 80     }
 81     b.insert(sumb);
 82     if (n % 2 == 0)flag = -1;
 83     else flag = 1;
 84     for (int i = n + 1; i <= m; ++i)
 85     {
 86         sumb *= -1;
 87         sumb += orib[i - n];
 88         sumb += orib[i] * flag;
 89         b.insert(sumb);
 90     }
 91     int ta, tb, tc;
 92     getbest(suma);
 93     for (int i = 1; i <= q; ++i)
 94     {
 95         cin >> ta >> tb >> tc;
 96         if ((tb - ta + 1) % 2 != 0)
 97         {
 98             if (ta & 1)suma += tc;
 99             else suma -= tc;
100         }
101         getbest(suma);
102     }
103     return 0;
104 }

 

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 64;
int a[maxn],b[maxn],c[maxn];
int main(){
    int n,m;read(n);read(m);
    char ch;
    for(int i=1;i<=n;++i){
        a[i] = b[i] = c[i] = 100000000;
        for(int j=0;j<m;++j){
            while(ch=getchar(),ch<'!');
            if(ch >= '0' && ch <= '9') a[i] = cat_min(a[i],cat_min(j,m-j));
            if(ch >= 'a' && ch <= 'z') b[i] = cat_min(b[i],cat_min(j,m-j));
            if(ch == '*' || ch == '#' || ch == '&') c[i] = cat_min(c[i],cat_min(j,m-j));
        }
    }
    int ans = 0x7f7f7f7f;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                if(i == j || j == k || i == k) continue;
                ans = cat_min(ans,a[i] + b[j] + c[k]);
            }
        }
    }
    printf("%d\n",ans);
    getchar();getchar();
    return 0;
}

memory limit per test

* 第一行: 房间数.

题解

我们要认清障碍物的停放是还是不是黄金年代致
那就是说我们直接剖断障碍物之间的间隔是或不是风姿罗曼蒂克律即可
鉴于这是个圆形跑道,所以数组[2,3,6]和[3,6,2]也是平等的
这正是说大家\(O(n^2)\State of Qatar枚举就能够

standard input

..................

problem B

Output

卫片(satel卡塔尔国

主题材料大体

在长度为m的圆形跑道上,起源区别的五人逆时针沿跑道跑大器晚成圈,得到了每一种人到它遇到的第1,2,...,n个障碍物的相距的数组。给出那五个数组,判定多人是否采取的叁个跑道。(全数的跑道长度均为m,但差异跑道障碍物放置差别State of Qatar

 

007

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 128;
int a1[maxn],a2[maxn],b1[maxn],b2[maxn];
int n;
inline int id(int x){
    if(x > n) x -= n;
    return x;
}
int main(){
    int m;read(n);read(m);
    for(int i=1;i<=n;++i) read(a1[i]);
    for(int i=1;i<=n;++i) read(a2[i]);
    for(int i=1;i<n;++i){
        b1[i] = a1[i+1] - a1[i];
    }b1[n] = m - (a1[n] - a1[1]);
    for(int i=1;i<n;++i){
        b2[i] = a2[i+1] - a2[i];
    }b2[n] = m - (a2[n] - a2[1]);
    //for(int i=1;i<=n;++i) printf("%d %d\n",b1[i],b2[i]);
    bool flag = false;
    for(int i=1,k;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(b1[i] == b2[j]){
                for(k=1;k<n;++k){
                    if(b1[id(i+k)] != b2[id(j+k)]) break;
                }
                if(k == n) flag = true;
            }
        }
    }
    if(flag) puts("YES");
    else puts("NO");
    getchar();getchar();
    return 0;
}

output

用字符矩阵来代表叁个8x8的棋盘,'.'表示是空格,'P'代表人质,'K'表示骑士。

难题大体:

给定n个长度为m的环状字符串,每一个字符串的首字符上有三个指南针,每一回操作可将随机叁个指针左移或右移1.问起码移动多少次使得全部被指针指向的字符能构成三个官方的字符串。(合法:存在数字、小写字母,特殊符号)

Input

 

5 6 3
1 2 3 4 5
1 2 3 4 5 6
1 1 10
1 1 -9
1 5 -1

3

After the first update a becomes {11, 2, 3, 4, 5} and it's optimal to choose j = 1, f(1) = |(11 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6) = |9| = 9.

......#.

Then output q lines, the i-th of them should contain the minimum value of the function f after performing the i-th update .

看了题解了才A掉的。。。(题解标程是C的。。晕。。看得累死)。

Note

#####..#

The first line contains three integers n, m and q (1 ≤ n ≤ m ≤ 105, 1 ≤ q ≤ 105) — number of elements in a, number of elements in b and number of queries, respectively.

多少中牛群不会包围另八个牛群或房间.

output

#.....#####.......     

Dr. Evil is interested in math and functions, so he gave Mahmoud and Ehab array a of length n and array b of length m. He introduced a function f(j) which is defined for integers j, which satisfy 0 ≤ j ≤ m - n. Suppose, c**i = a**i - b**i + j. Then f(j) = |c1 - c2 + c3 - c4... c**n|. More formally, 科技世界 2.

2

题意:a数组含有n个元素,b数组含有m个成分。含有q次区间校订,每一趟由公式科技世界 3计算f(j)最小值。

图上的一块相联接的 "#" 表示一群水牛或贰个房屋, 多个子"#" 连通的意味是说反正或左右相连.而下边的两块则是分手的:

After the third update a becomes {1, 1, 2, 3, 4} and it's optimal to choose j = 0, f(0) = |(1 - 1) - (1 - 2) + (2 - 3) - (3 - 4) + (4 - 5)| = |0| = 0.

  有三个N个节点的无根树,各节点编号为1..N,将来必要您剔除此中的多少个点,使分割开的连结块中节点个数都不当先原本的八分之四多。 

Dr. Evil wants Mahmoud and Ehab to calculate the minimum value of this function over all valid j. They found it a bit easy, so Dr. Evil made their task harder. He will give them q update queries. During each update they should add an integer x**i to all elements in a in range [l**i;r**i]i.e. they should add x**i to ali, ali + 1, ... , ari and then they should calculate the minimum value of f(j) for all valid j.

先是行:一个整数N,表示原子钟是10^N进制的。1 <= N <= 15。

input

 第大器晚成行:叁个整数N。

代码如下: