Hello 2019 自闭记
分类:
IT文章
•
2022-04-22 08:47:34
A:8min才过???
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
char 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
";
#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<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define N 20
char 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
";
#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<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
#define N 500010
char 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<int> 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
";
#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<b[N].size();i++) if (b[N][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<b[N-(i-N)].size()&&tail>=0&&b[i][tail]>=0)
{
while (head<b[N-(i-N)].size()&&i-N+b[N-(i-N)][head]<0) head++;
if (head>=b[N-(i-N)].size()) break;
tail--;head++;ans++;
}
}
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
View Code
D:暴力dp,对每个质因子做即可。看错题了一发???
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define P 1000000007
char 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
";
#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<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
View Code
F感觉非常神仙???过了很长时间才明白不是什么乱七八糟的线段树合并而是bitset啊???但还是不会啊???怎么这么多人过啊???叉人还被抢啊???自闭了啊???
result:rank 422 rating +12
F:显然只需要维护集合中每个数出现次数的奇偶性,考虑使用bitset。3操作非常难实现,可以考虑改为维护每个数的倍数的奇偶性,这样就相当于and了。然后考虑怎么以这种方式统计答案。使用莫比乌斯函数容斥即可。好思博啊怎么我不会啊???
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
#define N 100010
#define V 7001
bitset<V> 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<V;i++)
for (int j=i*i;j<V;j+=i*i)
mobius[j]=1;
for (int i=1;i<V;i++) mobius[i]^=1;
for (int i=1;i<V;i++)
for (int j=i;j<V;j+=i)
b[i][j]=mobius[j/i];
while (m--)
{
int op=read();
if (op==1)
{
int x=read(),y=read();a[x]=0;
for (int i=1;i*i<=y;i++)
if (y%i==0)
{
a[x][i]=1;
if (i*i!=y) a[x][y/i]=1;
}
}
if (op==2)
{
int z=read(),x=read(),y=read();
a[z]=a[x]^a[y];
}
if (op==3)
{
int z=read(),x=read(),y=read();
a[z]=a[x]&a[y];
}
if (op==4)
{
int x=read(),y=read();
printf("%d",(a[x]&b[y]).count()&1);
}
}
return 0;
}
//f[x]=Σcnt[d] d|x
//
View Code
#include<bits/stdc++.h>
using namespace std;
#define P 998244353 //当然原题的模数是1e9+7
#define N 100010
#define M 210
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,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<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);
for (int i=2;i<=n;i<<=1)
{
int wn=ksm(g,(P-1)/i);
for (int j=0;j<n;j+=i)
{
int w=1;
for (int k=j;k<j+(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<i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
}
fac[0]=1;for (int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%P;
inv[0]=inv[1]=1;for (int i=2;i<=m;i++) inv[i]=P-1ll*inv[P%i]*(P/i)%P;
for (int i=2;i<=m;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;
for (int i=0;i<(1<<9);i++) r[i]=(r[i>>1]>>1)|(i&1)*(1<<8);
for (int i=1;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
p2[0]=1;for (int i=1;i<=n;i++) p2[i]=(p2[i-1]<<1)%P;
dfs(1,1);
for (int i=1;i<=n;i++) inc(ans,f[i][m]);
cout<<ans;
return 0;
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define N 100010
char 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<int> 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
";
#else
const char LL[]="%lld
";
#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
",cnt);
for (int i=1;i<=cnt;i++)
{
printf("%d ",ans[i].size());
for (int j=0;j<ans[i].size();j++)
printf("%d ",ans[i][j]);
printf("
");
}
}
return 0;
}