2019牛客国庆集训派对day5

比赛链接
https://ac.nowcoder.com/acm/contest/1110#question
A
样例很友好,把唯一的特殊情况放在样例里头了。
就是-maxlonglong/-1是不能用longlong表示的,需要特判。
PS:该代码本地编译不通过,不知道原因,但提交后能AC。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
样例很友好,把唯一的特殊情况放在样例里头了。
就是-maxlonglong/-1是不能用longlong表示的,需要特判。 
PS:该代码本地编译不通过,不知道原因,但提交后能AC。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
ll a,b;
ll solve(){
    ll res1=a/b;
//  D(a);D(b);D(res1);E;
    if(a>=0&&b>0) return res1;
    if(a<=0&&b<0) return res1;
    if(a%b==0) return res1;
    return res1-1;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Simple Arithmetic.in","r",stdin);
    while(cin>>a>>b){
        if((a==-9223372036854775808) && (b==-1)){
            cout<<9223372036854775808<<endl;
            continue;
        }
        cout<<solve()<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

D
类似蓝书上可达性统计那道题,用bitset维护每个点可以到达的点的集合。
算法时间复杂度的重点在于:如果对于每个询问都进行一次拓扑排序,那么时间复杂度与边数有关,本题为稠密图,因此这样写会超时。
仔细观察,可以注意到当遍历完x的所有后继节点后,如果x的颜色为白色,那么x就可以作为他的所有后继节点中白色点,且为合法的路径的起点。
例如对于这组样例

9 10 2
7 1
7 3
1 2
8 9
1 3
2 4
4 3
3 5
3 6
2 3
1 

首先从7开始遍历,搜索完5,6,3,7四个点,对答案的贡献分别为0,0,2,3。
然后搜索9,8两个点,对答案的贡献分别为0,1。
之后搜索4,2两个点。从4搜索到3时,因为3已经被访问过了,所以可以直接返回,并对答案产生3的贡献。搜索2的时候同理,只要计算bitset[4]|bitset[2]中的1的数量即可。
即以2号点为起点的合法路径数为4。
于是总的答案就是2+3+1+3+4=13。
两个注意点:
必须要用向量存图,链式前向星会超时。
同时注意遍历x的出边的时候,千万不能写成i<=G[x].size()-1。
因为G[x].size()是无符号数,当G[x].size()=0时,G[x].size()-1会是一个很大的数。
代码如下

/*
类似蓝书上可达性统计那道题,用bitset维护每个点可以到达的点的集合。
算法时间复杂度的重点在于:如果对于每个询问都进行一次拓扑排序,那么时间复杂度与边数有关,本题为稠密图,因此这样写会超时。
仔细观察,可以注意到当遍历完x的所有后继节点后,如果x的颜色为白色,那么x就可以作为他的所有后继节点中白色点,且为合法的路径的起点。
例如对于这组样例
9 10 2
7 1
7 3
1 2
8 9
1 3
2 4
4 3
3 5
3 6
2 3
1 
首先从7开始遍历,搜索完5,6,3,7四个点,对答案的贡献分别为0,0,2,3。
然后搜索9,8两个点,对答案的贡献分别为0,1。 
之后搜索4,2两个点。从4搜索到3时,因为3已经被访问过了,所以可以直接返回,并对答案产生3的贡献。搜索2的时候同理,只要计算bitset[4]|bitset[2]中的1的数量即可。
即以2号点为起点的合法路径数为4。
于是总的答案就是2+3+1+3+4=13。 
两个注意点: 
必须要用向量存图,链式前向星会超时。
同时注意遍历x的出边的时候,千万不能写成i<=G[x].size()-1。
因为G[x].size()是无符号数,当G[x].size()=0时,G[x].size()-1会是一个很大的数。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<bitset>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int maxm=maxn*maxn/2;
const int INF=0x3f3f3f3f;
int n,m,Q;
int ans;
int c[maxn]; //颜色 0白 1黑 
vector<int>G[maxn];
void init(){
    for(int i=1;i<=n;i++) G[i].clear();
    memset(c,0,sizeof(c));
}
bitset<maxn+5>s[maxn+5];
int vis[maxn];
void dfs(int x){
    if(vis[x]) return;
    vis[x]=1;
    s[x].reset();
//  D(x);D(G[x].size()-1);E;
    for(int i=0;i<G[x].size();i++){ //这里千万不能写成i<=G[x].size()-1 因为G[x].size()是无符号数 当G[x].size()=0时 G[x].size()-1会是一个很大的数 
        int y=G[x][i];
//      if(vis[y]) continue;
        dfs(y);
        if(!c[x]) s[x]|=s[y];
    }
    if(!c[x]){
//      D(x);D(s[x].count()-1);E;
        s[x][x]=1; //对于白点 相当于自身可达 
        ans+=s[x].count()-1; //除去自身 
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Dynamic Graph.in","r",stdin);
    while(scanf("%d%d%d",&n,&m,&Q)!=EOF){
        int from,to;
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&from,&to);
            G[from].push_back(to);
        }
        int p;
        while(Q--){
            scanf("%d",&p);
            c[p]^=1;
            memset(vis,0,sizeof(vis));
            ans=0;
            for(int i=1;i<=n;i++){
                if(!vis[i]) dfs(i);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

E
用两个向量记录LIS转移时的所有前后继节点,然后通过n次bfs,来判断当一个点被影响时,后面必然会发生改变的所有点即可。
代码如下

/*
用两个向量记录LIS转移时的所有前后继节点,然后通过n次bfs,来判断当一个点被影响时,后面必然会发生改变的所有点即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
int n;
int f[maxn],a[maxn];
vector<int>v1[maxn],v2[maxn];//v1[i]表示LIS中i的所有前继节点 v2[i]表示LIS中i的所有后继节点 
queue<int>q;
int p[maxn]; //p[i]=-1表示被影响到 
void init(){
    for(int i=1;i<=n;i++) v1[i].clear(),v2[i].clear();
}
void dp(){
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<=i-1;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
        for(int j=1;j<=i-1;j++){
            if(a[i]>a[j]){
                if(f[i]==f[j]+1){
                    v1[i].push_back(j);
                    v2[j].push_back(i);
                }
            }
        }
    }
}
void solve(){
    for(int i=1;i<=n;i++){
        int ans=0;
        memset(p,0,sizeof(p));
        p[i]=-1;
        while(q.size()) q.pop();
        q.push(i);
        while(q.size()){ 
            int x=q.front();q.pop();
            for(int j=0;j<v2[x].size();j++){ //考虑x的所有后继节点y 
                int y=v2[x][j];
                int flag=0;
                for(int k=0;k<v1[y].size();k++){ //考虑当前y的所有前继节点z 
                    int z=v1[y][k];
                    if(p[z]!=-1){
                        flag=1;
                        break;
                    }
                }
                if(!flag){ //y的所有前继节点都被影响到了。因此只要改变了i,f[y]就一定会变成f[y]-1 
                    p[y]=-1;
                    q.push(y);
                }
            }
        }
        for(int j=1;j<=i-1;j++) ans^=(f[j]*f[j]); //i前面的数不会发生变化 
        for(int j=i+1;j<=n;j++){
            ans^=(f[j]+p[j])*(f[j]+p[j]); //后面的数字可能发生变化(不变或者减一) 
        }
        printf("%d ",ans);
    }
    printf("\n");
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Longest Increasing Subsequence.in","r",stdin);
    while(scanf("%d",&n)!=EOF){
        init();
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        dp();   
        solve();
    }
    return 0;
}

L
f[n]=\sum_{1\leq i < j <k<l\leq n}a_ia_ja_ka_l=\sum_{1\leq i < j <k<l\leq n-1}a_ia_ja_ka_l+a_n \sum_{1\leq i < j <k\leq n-1}a_ia_ja_k
g[n]=S(3,n)
f[n]=f[n-1]+a_ng[n-1]
计算g[n]的时候,预处理一下前缀和和6的逆元即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
ll f[maxn],g[maxn];
int n;
ll a[maxn],a1[maxn],a2[maxn],a3[maxn];
ll inv6;
ll ksm(ll A,ll B,ll p){
    ll res=1;
    while(B){
        if(B&1) res=(res*A)%p;
        B>>=1;
        A=(A*A)%p;
    }
    return res;
}
void dp(){
    for(int i=3;i<=n;i++){
        g[i]=(((((a1[i]*a1[i])%mod*a1[i])%mod-((3*a2[i])%mod*a1[i])%mod+mod)%mod+(2*a3[i])%mod)%mod)*inv6%mod;
        if(i>=4){
            f[i]=(f[i-1]+(a[i]*g[i-1])%mod)%mod;
        }
//      D(g[i]);D(f[i]);E;
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Nice Trick.in","r",stdin);
    inv6=ksm(6,mod-2,mod);
//  D(inv6);E;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            a1[i]=(a1[i-1]+a[i])%mod;
            a2[i]=(a2[i-1]+a[i]*a[i])%mod;
            a3[i]=(a3[i-1]+(a[i]*a[i])%mod*a[i])%mod;
        }
        dp();
        printf("%lld\n",f[n]);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,324评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,356评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,328评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,147评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,160评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,115评论 1 296
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,025评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,867评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,307评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,528评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,688评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,409评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,001评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,657评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,811评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,685评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,573评论 2 353