思维题 树状数组    发布于 2020-01-15   1011人围观   0条评论

题目大意

一开始有一个初始顺序的排列[1,n],一共有m次操作,每次将数ai从序列中取出,放到最开头的位置生成一个新的排列。

求问在所有过程中每一个数最小的下标位置和最大的下标位置。

题解

最小的下标位置是非常容易求得的,这很明显,因为如果从来没有被放到开头,那么答案一定是i,否则答案就是1。

需要思考的点在于求最大的下标位置。

这个数据范围不允许进行模拟,链表也不行(链表的单个操作、查询效率极差)。

先来考虑一种特殊情况1:

假设当前所有的数字都已经被放置到第一位过了,在满足这种条件后的最大的下标位置怎么求。

明显元素之间一开始的位置在哪里已经完全互不影响了。

如果一个数再被要求放到第一位,那么这个操作之前的下标位置可能就会影响答案。

而这个下标位置是什么?我们想什么样的操作会影响这个下标位置。很明显只有在上一次此数被放到第一位的时间之后,不同的数字放置到第一位才会使得这个数字的位置向后推移。也就是说,这个下标位置,就是当前未操作时刻和上一次这个数被放到第一位以后的时刻,这之间的不同数字的个数再+1,也就是区间内不同数的个数。

树状数组可以离线询问区间内不同数的个数。由于这道题的特殊性,我们无需对询问区间进行右端点优先排序,直接操作查询即可。

然后再考虑剩下的情况2:

如果一个数之前没有被放置在第一位的经历该如何计算?

这样在它被第一次放置到第一位的命令执行以前,其最大下标位置是之前的时刻被放置在第一位的大于此数的数字的个数 + 此数最初的坐标值。问题变成了维护区间内出现的不同数字的个数,需要用另外一个树状数组进行维护,只需要再每个数字第一次被放置在第一位时维护一次,查询一次即可。

在问题的最后,这样不一定已经求得最大值,因为对于每一个数字,最后可能有影响到最大值的问题但是没有查询更新。

所以在最后我们就要:

对于在操作序列中出现过的数字,我们执行情况1的查询一次。

对于未在操作序列中出现过的数字,我们执行情况2的查询一次。

代码

#include <bits/stdc++.h>
const int maxn = 3e5+5;
using namespace std;
map<int,int>mp;
int tr[maxn],a[maxn],ans[maxn],c[maxn];
int n,m;
int lowbit(int x){
	return x & (-x);
}
void add(int x,i
查看更多
思维题    发布于 2019-12-22   440人围观   1条评论

题目大意

给一个不完整的棋盘,每一列的方格数单调非升,问最多可以用多少个不重叠的1x2或者2x1的矩形覆盖棋盘(可以不完全覆盖)

题解

说实话思路比较巧妙

这种问题可以看成二分图匹配,相邻格子染色不同,假设分别染成黑白两种颜色,那么很明显想要用一个矩形覆盖,就必须要有一个黑格和一个白格匹配(两者相邻)。最大匹配数就是最终的答案。

但是这个数据范围过大,不能用匈牙利或者网络流解决。

注意到棋盘每一列的方格数是单调非升的,于是很明显只要先进行染色处理,然后从黑白格子中选出数量最少的那一种,其个数就是最大匹配数。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n;
long long ans;
long long a[maxn];
long long black,white;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        if(i & 1){
            black += a[i] / 2;
            white += (a[i] + 1) / 2;
        }
        else{
            black += (a[i] + 1) / 2;
            white += a[i] / 2;
        }
    }
    ans = min(black,white);
    cout << ans << endl;
    return 0;
}


查看更多
思维题 筛法    发布于 2019-09-11   470人围观   0条评论

题目大意

给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。

1≤ai≤1.5*108

题解

首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。

但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。

然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?
答案是否定的,这个可以通过打表来检查出来。

但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。

这样我们可以直接分开讨论,把所有可能的情况计入一个vector里面,最多出现1000种可能(实际上到不了),然后直接对于每一种可能暴力检索100个数是否符合要求即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int phi[maxn];
int pr[maxn],np[maxn];
int cnt = 0;
void euler(){
    phi[1] = 1;
    for(int i = 2;i < maxn;++i){
        if(!np[i]){
            pr[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= cnt && i * pr[j] < maxn;++j){
            np[i*pr[j]] = 1;
            if(i % pr[j] == 0){
                phi[i*pr[j]] = phi[i] * pr[j];
                break;
            }
            else phi[i*pr[j]] = phi[i] * (pr[j] - 1);
        }
    }
    return;
}
int mx = 0,mi = 1e9;
int a[105];
int n;
int t;
int calc(int x){//暴力求解φ(x
查看更多
Trie 思维题 hash    发布于 2019-09-06   469人围观   0条评论

题目大意

给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。

求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。

题解

暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。

而每一次失配我们都会重新回到起点。

于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,然后最终位置可以直接通过一个map存储hash值对应的trie树位置进行查询。

然后考虑如何预处理。

首先我们应该能够想到,如果一个子串能够在trie树中成功匹配,那么它的前缀串也一定能够在trie树中成功匹配。

于是这个性质导致我们可以二分失配的长度,然后我们只需要查询当前二分产生的子串是否能在trie树中进行匹配就可以了。

hash想不被卡的话,感觉就是选一个奇怪点的质数作为base。取模倒是不至于,直接unsigned long long自然溢出就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef unsigned long long ll;
const ll base = 983;
ll h[maxn],bs[maxn];
struct trie{
    int id;
    int ch[26];
}tr[maxn];
int f[maxn][26];
string s;
int x;char c;
int len;
map<ll,int>mp;
int n,m,q,t;
int ql,qr;
void init(){
    bs[0] = 1;
    for(int i = 1;i < maxn;++i){
        bs[i] = bs[i-1] * base;
    }
    return;
}
ll get_hash(int l,int r){
    return h[r] - h[l] * bs[r - l];
}
void dfs(int
查看更多
思维题 扫描线 树状数组    发布于 2019-09-02   782人围观   0条评论

题目大意

每个点的数值是通过一个从中心最大值开始的蛇形矩阵确定的。其中有m个点上的权值可用,对于q个询问,输出左下角为(x1,y1),右上角为(x2,y2)的矩阵区域内所有可用点的权值经过处理后的和。

处理的方法是,将原权值所有数位上的数相加。

题解

此题估计是模仿NOIP2014普及组T3的蛇形矩阵出的规律题目。

首先n为奇数,n*n为奇数,地图大小为 一定为奇数,所以

x = x − n/2 − 1
y = y  - n /2 - 1;
t = max(abs(x),abs(y)); //确定该点在第几圈螺旋
 if(x >= y)ans = n ∗ n −4∗ t ∗ t −2∗ t − x − y;//在向右与向上的路线上

else ans = n ∗ n −4∗ t ∗ t +2∗ t + x + y;//在向左与向下的路线上

(下面这部分代码是队友写的,我不是很清楚他的思路)

这样我们就可以O(m)的预处理所有的可用点的权值了。

对于每一次询问,都是一个矩形区域。

我们考虑二维前缀和,其答案相当于ans(x2,y2) - ans(x2,y1-1) - ans(x1-1,y2) + ans(x-1,y-1),其中ans(x,y)代表1——x,1——y矩形区域中所有值的和。

但是二维显然会爆空间,所以我们考虑如何降维。

我们可以将一个询问拆解成4个,用flag为1或-1标记此次询问的前缀和是要加还是减。

之后我们可以运用扫描线的方法,先按照x排序,然后对y进行映射,用树状数组维护映射后y上的值。用一条竖直的扫描线不断向右扫,遇到一个询问点就查询一次。

但是这样我们使用扫描线是要将所有的点当作修改操作的,而不能提前加入树状数组,否则答案会出问题。

所以我们将所有的m个点和4*q个询问加入操作合集,查询flag为-1或1,修改flag为2,按照先x、次先y、再次先修改的顺序排序,用一条平行于y轴的线从左向右扫过整个横坐标区间,用树状数组维护当前投影到y轴上的值。每当遇到修改操作,直接update树状数组中的值进行维护,遇到查询操作直接从树状数组中查询。

理论时间复杂度为O((m+4*q)log(m+4*q));

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(int x, int y, int n
查看更多
思维题    发布于 2019-08-27   730人围观   0条评论

题目大意

n个人围成一圈,从1号开始报数,报到k的人出圈,然后再从下一个人开始新一轮报数。问经过第m个出圈的人最开始的编号是多少。

题解

经典约瑟夫问题,想必大家都知道递推式吧……

f(n,m) = (f(n-1,m-1) + k) % n

好了就是这样,至于具体证明貌似说刘汝佳的白书上有?

但是我们注意到此题数据范围真的是太大了,我们不能使用O(m)的做法了……

不,并不是不能用,只是当m小于等于k的时候我们可以这么做(这时候m的范围只有2x106),但是如果是k小于等于m的时候我们就要另作讨论了。

首先如果k = 1,那我们直接输出m就好,因为题目保证n ≥ m;

但是如果k > 1……

我们注意到,如果k比较小,远小于n-m的话,我们可能进行d轮都轮不完一圈,所以我们考虑可以用乘法跳项的思想来加速递推式的推进。

最终的复杂度不是很清楚是多少,但是由于使用了乘法来加速,所以我们中间实际上跳过了很多不必要取模的项,整体复杂度就比较低了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
int t;
ll d,now,a;
ll ans = 0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    int cas = 0;
    while(t--){
        cas++;
        ans = 0;
        cin >> n >> m >> k;
        ll ans = (k - 1) % (n - m + 1) + 1;
        if(k == 1){
            ans = m;
        }
        else if(k >= m){
            for(ll i = 2;i <= m;++i)
                ans = (ans + k - 1) % (n - m + i) + 1;
        }
        else{
            now = 1,a = n - m;
            while(now < m){
           
查看更多
思维题    发布于 2019-08-20   388人围观   0条评论

题目大意

给n个数,两个数如果能取并运算不为0则又一条边相连,求长度至少为3的最小环的长度,若没有环,输出-1。

题解

md这题我挂了7发,真是sb……

首先我们先从大到小排序,把0去掉,因为0不会和任何数连边。

然后我们考虑二进制并运算,只有两个数某个二进制位相同时,两个数才会连边。

而如果有至少三个数二进制的第i位同时为1时,这些点互相之间都会连边,那么一定会形成环,最小环的长度为3。

所以我们可以对所有非0数进行二进制分解,记录每个二进制位上会出现多少次,如果其中有一个大于等于3,则说明最小环的长度为3。

那么如果没有以上的点就一定答案为-1吗?并不是。

那该怎么做?

如果我们仔细观察,所有数进行二进制分解以后,最多不会超过64位。

所以我们可以根据鸽巢原理得出结论:如果非0的数字超过128个一定会出现长度为3的最小环。

所以说如果我们二进制位检查未能检查出答案,那么只有非0数字在128个及以下的时候,有可能还会存在环。

如果出现这种情况,我们直接暴力建边然后dfs求出最小环(tarjan也可以,不过注意是无向图),如果还是求不出环的话,那么就说明不存在环,直接输出-1。

这个题思路还是蛮巧妙的。其实竞赛中还是有不少的题目是分数据个数搞不同做法的。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
typedef long long ll;
ll a[maxn];
int p[105];
const int INF = 1e9;
void work(ll x){
    int cnt = 0;
    while(x > 0){
        if(x % 2 == 1)p[cnt]++;
        x /= 2;
        cnt++;
    }
    return;
}
const int maxm = 1e3+5;
vector<int>g[maxm];
int vis[maxm];
int tag[maxm];
int ans = 0;
int tot = 0;
int pre[maxm];
void dfs(int now,int fa){
    vis[now] = 1;
    for(int i = 0;i < g[now].size();++i
查看更多
博弈论 贪心 思维题    发布于 2019-08-13   473人围观   0条评论

题目大意

先手有n张牌,后手有m张牌,如果某人打出了某种颜色的牌,那么另一个人就不能打这种颜色的牌,最后不能出牌的人输。求问是先手胜还是后手胜。

题解

两人都是按最优策略取的博弈,不过和SG函数并没有什么关系。

两个人肯定每回合都是贪心的取对自己最有利的方案。

首先我们将两人都有的颜色的牌抽出来,剩下的就是两人各自独立的牌集,不会受对方出牌的影响。

然后我们考虑被抽出来的牌,怎样取能使得局面变得对自己有利。

如果对于某种颜色,两人共有的这种颜色的牌比较大,那么当前的出牌者选择出这种颜色的牌的优先级肯定就更高。

然后当前的人出一种颜色的牌,就可以看成是把自己原有的这种颜色的牌全部收回,把对方原有的这种颜色的牌全部丢掉。

所以我们需要离散化颜色,然后对于公共颜色的牌全部抽出,然后按照两人手中的这种颜色的牌的总数从大到小排序,然后让先手先选,后手后选直到全部选完。

选完后我们比较一下两人手里的牌的总数。

如果先手手中的牌比后手多,则先手必胜,否则先手必败。

(对于我取消流同步的cin比自己写的快读要快这件事,我真的很疑惑……)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 1e5+5;
int a[maxn],b[maxn];
unsigned long long mod;
unsigned long long k1, k2;
unsigned long long rng() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
int t;
int n,m,p;
int cnt = 0;
int c[maxn<<1];
int q[maxn<<1];
int com[maxn<<1];
struct point{
    int val,id;
}e[maxn];
bool cmp(point a,point b
查看更多
思维题    发布于 2019-08-13   478人围观   0条评论

题目大意

一场考试有n个题目,总共为m分,如果要通过一个分值为x的题目,需要复习x+1小时。

现在目标为通过至少k个题目,求问至少要复习多长时间。

题解

首先我们从出题老师的角度来看,怎么样才能让考生无法通过考试呢。

当然是让学生复习时间最少的n-k+1门科目不能通过考试,也就是要求让他们的复习时间恰好等于复习分数。

然后镜头转回学生,我们需要复习时间最少的n-k+1门复习时间最少的科目中有1门能通过就好了。

所以最后的答案是(m/(n-k+1)+1) *(k-1)+m+1.

代码

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
int T;
ll n, m, k;
int main(){
    scanf("%d", &T);
    while (T--){
        scanf("%lld%lld%lld", &n, &m, &k);
        ll p = m / (n - k + 1) + 1;
        ll ans = p * (k-1) + m + 1;
        printf("%lld\n",ans);
    }
    return 0;
} 


查看更多
思维题    发布于 2019-08-05   388人围观   0条评论

题目大意

给出n个二元组(ai,bi),求出Σni=1|aix-bi| = c 的所有解,并用最简分数形式表示,若有无穷多解输出-1

题解

这道题卡我常……比赛的时候被卡常卡到心态炸裂

赛后发现我被排序用的cmp函数给卡了,真TM没想到啊……

首先我们不能直接求绝对值方程式的解,我们通常的想法是把绝对值号拿掉,然后再做。

但是这题一共有n个绝对值式,不是很好办。

我们想一下,每一个绝对值式都有一个对应的变号点,我们可以先把这些变号点求出来,然后根据变号点对每个式子排一遍序。

然后很明显的这些变号点把整个数轴分成了n+1个区间。每个区间对应了一个去掉绝对值后的方程式,也对应着一个合法的解区间。

然后我们对于每一个解区间所对应的无绝对值方程式,可以解出确切的一个解x’,或者解出无数组解。如果解出确切的一个解x‘,我们只需要判断x’是否在当前的合法解区间内即可。

至于解区间间的方程式变换,由于我们已经对式子排了序,也就是确定了每个式子变号点的前后顺序,所以可以做到O(1)变换方程式。

总复杂度O(T*(nlogn + n))

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int p[maxn],q[maxn];
int tot = 0;
struct funct{
    int a,b;
    double k;
}f[maxn];
const double eps = 1e-5;
bool cmp(funct x,funct y){
    return x.k - y.k >= eps;
}
int T;
int n;
int suma,sumb;
int c;
int x,y,g;
bool flag;
double xx,yy;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&c);
        tot = 0;
        suma = 0;
        su
查看更多