博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Hello 2019 自闭记
阅读量：5122 次
发布时间：2019-06-13

本文共 10125 字，大约阅读时间需要 33 分钟。

　　A：8min才过？？？

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define int long longchar getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ char a=getc(),b=getc(); for (int i=0;i<5;i++) { char x=getc(),y=getc(); if (a==x||b==y) {cout<<"YES";return 0;} } cout<<"NO"; return 0; //NOTICE LONG LONG!!!!!}
View Code

　　B：WA了一发？？？

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define int long long#define N 20char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N];bool flag=0;void dfs(int k,int s){ if (flag) return; if (k>n&&s==0) {flag=1;return;} if (k>n) return; dfs(k+1,(s+a[k])%360); dfs(k+1,(s-a[k]+360)%360);}signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ n=read(); for (int i=1;i<=n;i++) a[i]=read(); dfs(1,0); if (flag) cout<<"YES";else cout<<"NO"; return 0; //NOTICE LONG LONG!!!!!}
View Code

　　C：多余匹配括号去掉后设右括号个数为x，左括号个数为y，则匹配的括号序列对要求y1+y2=0 x1=0 y1+x2=0，瞎贪贪就行了。RE了一发40min才过？？？

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define int long long#define N 500010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,ans;char s[N];vector
             
               b[N<<1];struct data{ int x,y;}a[N];signed main(){#ifndef ONLINE_JUDGE freopen("c.in","r",stdin); freopen("c.out","w",stdout); const char LL[]="%I64d\n";#endif n=read(); for (int i=1;i<=n;i++) { scanf("%s",s+1);int m=strlen(s+1); int cnt=0; for (int j=1;j<=m;j++) { if (s[j]=='(') cnt++;else cnt--; a[i].x=min(a[i].x,cnt); } a[i].y=cnt; b[a[i].y+N].push_back(a[i].x); } // y1+y2=0 y1+x2>=0 for (int i=0;i<(N<<1);i++) sort(b[i].begin(),b[i].end()); int cnt=0; for (int i=0;i
              
               =0) cnt++; ans=cnt/2; for (int i=N+1;i<(N<<1);i++) { int head=0,tail=b[i].size();tail--; while (head
               
                =0&&b[i][tail]>=0) { while (head
                
                 <0) head++; if (head>=b[N-(i-N)].size()) break; tail--;head++;ans++; } } cout<
View Code

　　D：暴力dp，对每个质因子做即可。看错题了一发？？？

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define P 1000000007char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}ll n,prime[100];int m,cnt[100],a[100],f[100][100],g[10010][100],inv[110],t,tot=1,ans=0;int ksm(int a,int k){ int s=1; for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P; return s;}void dfs(int k,ll s,ll u){ if (k>t) {ans=(ans+s%P*u)%P;return;} for (a[k]=0;a[k]<=cnt[k];a[k]++) { dfs(k+1,s,u*f[k][a[k]]%P); s*=prime[k]; }}signed main(){#ifndef ONLINE_JUDGE freopen("d.in","r",stdin); freopen("d.out","w",stdout); const char LL[]="%I64d\n";#endif cin>>n>>m; for (int i=2;1ll*i*i<=n;i++) if (n%i==0) { t++;prime[t]=i; while (n%i==0) cnt[t]++,n/=i; } if (n>1) prime[++t]=n,cnt[t]=1; for (int i=1;i<=100;i++) inv[i]=ksm(i,P-2); for (int i=1;i<=t;i++) { memset(g[0],0,sizeof(g[0]));g[0][cnt[i]]=1; for (int j=1;j<=m;j++) { g[j][cnt[i]+1]=0; for (int k=cnt[i];k>=0;k--) g[j][k]=(g[j][k+1]+1ll*g[j-1][k]*inv[k+1])%P; } for (int k=0;k<=cnt[i];k++) f[i][k]=g[m][k]; } //for (int i=1;i<=t;i++) tot=1ll*tot*C[cnt[i]+m][cnt[i]]%P;tot=inv(tot); dfs(1,1,1); //cout<<1ll*ans*tot%P; cout<
View Code

　　F感觉非常神仙？？？过了很长时间才明白不是什么乱七八糟的线段树合并而是bitset啊？？？但还是不会啊？？？怎么这么多人过啊？？？叉人还被抢啊？？？自闭了啊？？？

　　result：rank 422 rating +12

　　F：显然只需要维护集合中每个数出现次数的奇偶性，考虑使用bitset。3操作非常难实现，可以考虑改为维护每个数的倍数的奇偶性，这样就相当于and了。然后考虑怎么以这种方式统计答案。使用莫比乌斯函数容斥即可。好思博啊怎么我不会啊？？？

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define N 100010#define V 7001bitset
             
               a[N],b[V];int n,m,mobius[V];int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int main(){#ifndef ONLINE_JUDGE freopen("f.in","r",stdin); freopen("f.out","w",stdout);#endif n=read(),m=read(); for (int i=2;i
View Code

　　G：先考虑k=1时怎么做。设f[i][1]为i作为斯坦纳树（暂且就这么叫）的根（该点不一定被选中）时所有方案边数之和，f[i][0]为上述方案数；g[i][1]为i作为斯坦纳树的根（但目前选中的点的斯坦纳树实际上并不将其包含，且选中点集不为空）时所有方案边数之和，g[i][0]为上述方案数。转移考虑f必须是选中根或至少选中两棵子树，g只选中一棵子树。f可以不考虑限制后再减掉g。这个沙雕dp已经想了我2h了。

　　然后考虑怎么求k次方。容易想到在dp中记录各次方，（事实上刚才的dp中就记录了0次方和1次方）具体转移由二项式定理即可得，注意细节。那么暴力复杂度是O(nk2)，NTT优化后可以做到O(nklogk)。复杂度看上去就很不靠谱，并且甚至题就没给NTT模数。（但还是有神仙用NTT过掉了）

#include
      
       using namespace std;#define P 998244353 //当然原题的模数是1e9+7 #define N 100010#define M 210int read(){    int x=0,f=1;char c=getchar();    while (c<'0'||c>'9') {
    if (c=='-') f=-1;c=getchar();}    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();    return x*f;}int n,m,p[N],f[N][M],g[N][M],size[N],C[M][M],fac[M],inv[M],p2[N],tmp[M],a[1<<9],b[1<<9],r[1<<9],t,ans,inv3,inv512;struct data{
    int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void inc(int &x,int y){x+=y;if (x>=P) x-=P;}int ksm(int a,int k){    int s=1;    for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;    return s;}int INV(int a){
    return ksm(a,P-2);}void DFT(int *a,int n,int g){    for (int i=0;i
       
        >1);k++,w=1ll*w*wn%P)            {                int x=a[k],y=1ll*w*a[k+(i>>1)]%P;                a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P;            }        }    }}void mul(int *a,int *b){    DFT(a,1<<9,3),DFT(b,1<<9,3);    for (int i=0;i<(1<<9);i++) a[i]=1ll*a[i]*b[i]%P;    DFT(a,1<<9,inv3);    for (int i=0;i<(1<<9);i++) a[i]=1ll*a[i]*inv512%P;}void dfs(int k,int from){    f[k][0]=2;size[k]=1;    for (int i=p[k];i;i=edge[i].nxt)    if (edge[i].to!=from)    {        dfs(edge[i].to,k);        memset(a,0,sizeof(a)),memset(b,0,sizeof(b));        for (int j=0;j<=m;j++) a[j]=inv[j],b[j]=1ll*inv[j]*(f[edge[i].to][j]+g[edge[i].to][j])%P;        mul(a,b);for (int j=0;j<=m;j++) tmp[j]=1ll*a[j]*fac[j]%P;        for (int j=0;j<=m;j++) inc(g[k][j],tmp[j]);        memset(a,0,sizeof(a));memset(b,0,sizeof(b));        for (int j=0;j<=m;j++) a[j]=1ll*inv[j]*f[k][j]%P,b[j]=1ll*inv[j]*tmp[j]%P;        mul(a,b);for (int j=0;j<=m;j++) tmp[j]=1ll*a[j]*fac[j]%P;        for (int j=1;j<=m;j++) inc(f[k][j],tmp[j]);        f[k][0]=p2[size[k]+=size[edge[i].to]];    }    for (int j=0;j<=m;j++) inc(f[k][j],P-g[k][j]);    f[k][0]--;}int main(){#ifndef ONLINE_JUDGE    freopen("g.in","r",stdin);    freopen("g.out","w",stdout);#endif    n=read(),m=read();inv3=INV(3),inv512=INV(512);    C[0][0]=1;    for (int i=1;i<=m;i++)    {        C[i][0]=C[i][i]=1;        for (int j=1;j
        
         >1]>>1)|(i&1)*(1<<8);    for (int i=1;i
View Code

　　换一种思路。https://www.cnblogs.com/Gloid/p/9553291.html 我们想起来还做过这么个题。搬上同样的做法即可。然后我发现我不会转移了，就非常开心的弃掉了。

　　E：见官方题解及讨论区一楼补充。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define ll long long#define N 100010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,n,a[N],b[N],f[N],q[N],cnt;bool flag[N];vector
             
               ans[N],tmp[N];int solve(int op){ for (int i=1;i<=n;i++) q[i]=0; int tail=0;tmp[0].clear(); for (int i=1;i<=n;i++) { int l=0,r=tail,ans=0; while (l<=r) { int mid=l+r>>1; if (a[i]>a[q[mid]]) ans=mid,l=mid+1; else r=mid-1; } f[i]=q[ans];ans++;if (ans>tail) {tail++;if (op) tmp[tail].clear();} q[ans]=i;if (op) tmp[ans].push_back(a[i]); } if (op) for (int i=1;i<=tail;i++) ans[++cnt]=tmp[i]; return tail;}int main(){#ifndef ONLINE_JUDGE freopen("e.in","r",stdin); freopen("e.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif T=read(); while (T--) { n=read(); for (int i=1;i<=n;i++) a[i]=read(); cnt=0; while (n) { int LIS=solve(0),end_LIS=q[LIS]; for (int i=1;i<=n;i++) flag[i]=0; if ((1ll*LIS*(LIS+1)>>1)>n) { cnt++;ans[cnt].clear(); int x=end_LIS; while (x) { ans[cnt].push_back(a[x]); flag[x]=1;x=f[x]; } reverse(ans[cnt].begin(),ans[cnt].end()); int m=0; for (int i=1;i<=n;i++) if (!flag[i]) b[++m]=a[i]; n=m;for (int i=1;i<=n;i++) a[i]=b[i]; } else {solve(1);break;} } printf("%d\n",cnt); for (int i=1;i<=cnt;i++) { printf("%d ",ans[i].size()); for (int j=0;j
View Code

 

转载于:https://www.cnblogs.com/Gloid/p/10223280.html

你可能感兴趣的文章
myeclipse插件安装
查看>>
浙江省第十二届省赛 Beauty of Array（思维题）
查看>>
NOIP2013 提高组 Day1
查看>>
cocos2dx 3.x simpleAudioEngine 长音效被众多短音效打断问题
查看>>
存储（硬件方面的一些基本术语）
查看>>
观察者模式
查看>>
Weka中数据挖掘与机器学习系列之基本概念（三）
查看>>
Win磁盘MBR转换为GUID
查看>>
大家在做.NET B/S项目的时候多用什么设技术啊？
查看>>
Java SE和Java EE应用的性能调优
查看>>
Android设计模式系列--原型模式
查看>>
免费的论文查重网站
查看>>
C语言程序第一次作业
查看>>
leetcode-Sort List
查看>>
中文词频统计
查看>>
了解node.js
查看>>
想做移动开发，先看看别人怎么做
查看>>
Eclipse相关集锦
查看>>
虚拟化架构中小型机构通用虚拟化架构
查看>>
继承条款effecitve c++ 条款41-45
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-18 11:32:39   当前IP: 3.15.206.88   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我