官方题解：https://ac.nowcoder.com/discuss/208642?type=101&order=0&pos=9&page=1
A ： Equivalent Prefixes
题目链接 ： https://ac.nowcoder.com/acm/contest/881/A
题解：
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 100005
#define MAXN 1000010
#define N 100050
using namespace std;
const ull inf = 1LL << 61;
const long long mod=1e9+7;//注意两数相减加一个mod
const double PI=acos(-1);
const double eps=1e-5;
double gcd(double a,double b)
{
return (!b)?a:gcd(b,(long long)a%(long long)b);
}
double lcm(double a,double b)
{
return a/gcd(a,b)*b;
}
int dp1[maxn][20];
int dp2[maxn][20];
int arr1[maxn];
int arr2[maxn];
bool check(int l,int r)
{
if(l>r) return 1;
int k=log2(r-l+1);
int r1=arr1[dp1[l][k]]<arr1[dp1[r-(1<<k)+1][k]]?dp1[l][k]:dp1[r-(1<<k)+1][k];
int r2=arr2[dp2[l][k]]<arr2[dp2[r-(1<<k)+1][k]]?dp2[l][k]:dp2[r-(1<<k)+1][k];
if(r1!=r2) return 0;
return check(l,r1-1)&&check(r1+1,r);
}
int main()
{
//freopen("d:in.txt","r",stdin);
//freopen("d:out.txt","w",stdout);
priority_queue <int,vector<int>,less<int> > p1,p2;
priority_queue <int,vector<int>,greater<int> > q;
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) scanf("%d",&arr1[i]);
for(int i=1;i<=n;i++) scanf("%d",&arr2[i]);
for(int i=1;i<=n;i++) {dp1[i][0]=i;dp2[i][0]=i;}
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
int u,v;
u=dp1[i][j-1];v=dp1[i+(1<<(j-1))][j-1];
dp1[i][j]=arr1[u]<arr1[v]?u:v;
u=dp2[i][j-1];v=dp2[i+(1<<(j-1))][j-1];
dp2[i][j]=arr2[u]<arr2[v]?u:v;
}
int l=1,r=n+1;
while(l<r-1)
{
int mid=(l+r)/2;
if(check(1,mid)) l=mid;
else r=mid;
}
cout<<l<<endl;
}
return 0;
}
B Integration
题目链接：https://ac.nowcoder.com/acm/contest/881/B
题目描述：
题解：
思路： https://blog.csdn.net/qq_41730082/article/details/96443875
c++代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<set>
#include<map>
#include <assert.h>
#include<stack>
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
LL mod=1e9+7;
const double PI=acos(-1.0);
const double eps=1e-10;
void quickread(){std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int lowbit(int x){return x&(-x);}
LL a[1004];
LL c[1004];
LL quick(LL x,LL n)
{
LL ans=1;
while(n)
{
if(n%2) ans=ans*x%mod;
n/=2;
x=x*x%mod;
}
return ans;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++ )scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
{
LL sum=1;
for(int j=1;j<=n;j++)
{
if(i==j ) continue;
else{
sum=sum*((a[j]*a[j]%mod-a[i]*a[i]%mod)+mod)%mod;
}
}
sum=quick(sum,mod-2);
c[i]=sum;
}
LL ans=0;
for(int i=1;i<=n;i++)
{
ans=(ans+c[i]*quick(2*a[i],mod-2)%mod)%mod;
}
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
C : Euclidean Distance
题目描述 ：
题解：
C++ 代码：
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a": " << a << endl;
#define mst(a, b) memset(a, b, sizeof(a))
#define ALL(x) x.begin(), x.end()
#define lc rt << 1
#define rc rt << 1 | 1
#define X first
#define Y second
inline int lowbit(int x) { return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
typedef pair<int, int> pii;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
const int mod = 1e9 + 7;
LL a[N];
LL pre[N];
int main() {
#ifdef purple_bro
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
for (;cin >> n >> m;) {
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n, [](int a, int b) -> bool {
return a > b;
});
pre[0] = -m;
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];
int now = n;
for (int i = 1; i < n; i++) if (pre[i] > a[i + 1] * i) {
now = i;
break;
}
LL t = pre[now] * pre[now];
LL d = now;
for (int i = now + 1; i <= n; i++)
t += a[i] * a[i] * d;
d *= m * m;
LL gcd = __gcd(t, d);
t /= gcd; d /= gcd;
if (d == 1 || !t)
cout << t << "\n";
else
cout << t << "/" << d << "\n";
}
return 0;
}
D: Parity of Tuples
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll i,j,u,vv,n,m,k,a[11],kp,dp[1048576],inv2,v[1024],l[1024],pk,pt,cnt[1048576],pm;
ll lowbit(ll p){return p&-p;}
ll M(ll p)
{
if(p<0)return p+mod;
if(p>=mod)return p-mod;
return p;
}
ll pow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main()
{
inv2=pow(2LL,mod-2LL);
cnt[0]=1;
for(i=1;i<(1<<20);i++)cnt[i]=-cnt[i-lowbit(i)];
while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
{
//init();
for(i=0;i<(1<<k);i++)dp[i]=0;
pk=0;
for(i=1;i<=n;i++)
{
v[0]=0;
for(j=1;j<=m;j++)scanf("%lld",&a[j]),v[1<<(j-1)]=a[j];
dp[0]+=1;l[0]=1;
for(j=1;j<(1<<m);j++)
{
kp=lowbit(j);
v[j]=v[j-kp]^v[kp];
l[j]=-l[j-kp];
dp[v[j]]+=l[j];
//printf("%lld %lld %lld\n",j,v[j],l[j]);
}
}
for(i=0;i<(1<<k);i++)dp[i]=M(dp[i]*cnt[i]);
for(i=0;i<k;i++)
{
for(j=0;j<(1<<k);j++)
{
if(j&(1<<i))
{
u=dp[j];vv=dp[j-(1<<i)];
dp[j]=M(u+vv);
dp[j-(1<<i)]=M(vv-u);
}
}
}
//for(i=0;i<(1<<k);i++)printf("%lld %lld\n",i,dp[i]);
pm=pow(inv2,m);
for(i=0,pt=1;i<(1<<k);i++,pt=pt*3%mod)pk^=dp[i]*pm%mod*pt%mod;
printf("%lld\n",pk);
}
return 0;
} E : ABBA
样例：
20 36
40 69
100 1000
1000 200
200 99
99 1
1 2
0 1dp1
0 2dp1
1 0dp1
1 1dp2
1 2dp3
1 3dp4
2 1dp3
2 2dp6
2 3dp10
3 1dp4
3 2dp10
3 3dp20
20 36
677063087
40 69
357970915
100 1000
651709122
1000 200
946791934
200 99
568337085
99 1
554042848
#include <iostream>
#include <cstring>
using namespace std;
#define MOD 1000000007
int dp[3000][3000];
int main()
{
int n, m;
while(cin >> n >> m)
{
for(int i = 0; i <= n + m; ++i)
{
for(int j = 0; j <= n + m; ++j)
{
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for(int i = 1; i <= m; ++i)
{
dp[0][i] = 1;
}
for(int i = 1; i <= n; ++i)
{
dp[i][0] = 1;
}
for(int i = 1; i <= n + m; ++i)
{
for(int j = 1; j <= n + m; ++j)
{
if(i <= n + j&&j <= m + i)
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%MOD;
}
}
cout << dp[n + m][n + m]<<endl;
}
return 0;
}
/*
20 36
40 69
100 1000
1000 200
200 99
99 1
1 2
0 1dp1
0 2dp1
1 0dp1
1 1dp2
1 2dp3
1 3dp4
2 1dp3
2 2dp6
2 3dp10
3 1dp4
3 2dp10
3 3dp20
20 36
677063087
40 69
357970915
100 1000
651709122
1000 200
946791934
200 99
568337085
99 1
554042848
*/
F : Random Point in Trangle
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int x1, y1, x2, y2, x3, y3;
while (cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
ll a = x2 - x1, b = y2 - y1;
ll c = x3 - x1, d = y3 - y1;
ll ans = abs(a * d - b * c);
cout << ans * 11 << '\n';
}
}
G : Substrings 2
#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define pb push_back
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=5e4+10;
const int M=300;
const ll mo=998244353;
const ll D=18113219;
const ll DL=181321;
ll pw[M],s[N][M],nw[N][M];int n,m,b[N],l[N],r[N];
inline bool cmp(int x,int y){
rep(i,0,m)if(s[x][i]!=s[y][i]){
rep(j,0,m){int p=m*i+j;
if(x+p>n)return 1;
if(y+p>n)return 0;
int X=l[x+p]<x?0:l[x+p]-x+1;
int Y=l[y+p]<y?0:l[y+p]-y+1;
if(X<Y)return 1;
if(X>Y)return 0;
}
}return 0;
}
void sol(){
if(scanf("%d",&n)==EOF)exit(0);
map<int,int>mp;m=sqrt(n)+1;
rep(i,1,n){int x;
scanf("%d",&x);
if(mp[x])r[mp[x]]=i;
l[i]=mp[x];r[i]=0;mp[x]=i;
}
rep(i,0,m)nw[n][i]=s[n][i]=0;
s[n][0]=DL;
dep(i,n-1,1){ll ls=DL;bool lf=0;
rep(j,0,(n-i)/m){
int p=i+(j+1)*m,c;
nw[i][j]=(nw[i+1][j]*D+lf)%mo;lf=0;
if(r[i]&&(r[i]-i)/m==j)(nw[i][j]+=pw[r[i]-(i+j*m)])%=mo;
if(p<=n&&l[p]>i){
lf=1;(nw[i][j]+=mo-pw[m])%=mo;
}
if(p<=n){
if(l[p]<=i)c=DL;else c=DL+l[p]-i;
}else c=0;
s[i][j]=(s[i+1][j]*D+mo-c*pw[m]%mo+ls+nw[i][j])%mo;ls=c;
}
}
rep(i,1,n)b[i]=i;
sort(b+1,b+n+1,cmp);
ll ans=n-b[1]+1;
rep(i,2,n){int lcp=0;
rep(j,0,m)if(s[b[i-1]][j]!=s[b[i]][j]){
rep(k,0,m){int p=m*j+k;
if(max(b[i-1],b[i])+p>n||
(l[b[i-1]+p]<b[i-1]?0:l[b[i-1]+p]-b[i-1]+1)
!=(l[b[i]+p]<b[i]?0:l[b[i]+p]-b[i]+1))break;
++lcp;
}break;
}else lcp+=m;
ans+=n-b[i]-lcp+1;
}
printf("%lld\n",ans);
}
int main(){pw[0]=1;
rep(i,1,M-1)pw[i]=pw[i-1]*D%mo;
for(;;)sol();
}
H: XOR
具体题面：https://blog.csdn.net/u013534123/article/details/96482572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN=63;
const int mod=1000000007;
ll num[100005];
struct LinearBase {
ll base[MN];
bool flag;//该线性基能否表示0
int cnt;
void Copy(LinearBase b) {
cnt=b.cnt;
flag=b.flag;
memcpy(base,b.base,sizeof(base));
}
void Clear() {
cnt=0;
flag=false;
memset(base,0,sizeof( base));
}
//尝试向线性基中插入一个值
void Insert(ll x) {
for(int i=MN; ~i; i--)
if(x&(1ll<<i))
if(!base[i]) {
base[i]=x;
cnt++;
return;
} else
x^=base[i];
flag=true;
}
//判断该线性基能否表示x
bool Check(ll x) {
for(int i=MN; ~i; i--)
if(x&(1ll<<i)) {
if(!base[i])
return false;
else
x^=base[i];
}
return true;
}
} B1,B2,B3;
ll qpow(ll x,int n) {
ll res=1;
while(n) {
if(n&1)
res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
ll ans,p2;
vector<int>B1ID;
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
//freopen("Yinku.out", "w", stdout);
#endif // Yinku
int n;
while(~scanf("%d", &n)) {
//cout<<"0.\n";
for(int i=1; i<=n; i++) {
scanf("%lld",&num[i]);
}
B1.Clear();
B2.Clear();
B1ID.clear();
for(int i=1; i<=n; i++) {
if(B1.Check(num[i])) {
B2.Insert(num[i]);
} else {
B1.Insert(num[i]);
B1ID.push_back(i);
}
}
ans=0;
if(n!=B1.cnt) {
p2=qpow(2,n-B1.cnt-1);
ans+=p2*(n-B1.cnt)%mod;
}
for(ll i:B1ID) {
B3.Copy(B2);
for(ll j:B1ID) {
if(i!=j) {
B3.Insert(num[j]);
}
}
if(B3.Check(num[i])) {
//num[i]能被其他数表示
ans=(ans+p2)%mod;
}
}
printf("%lld\n", ans);
}
}
I题
Points Division
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100010;
const ll inf=1000000000000007ll;
#define ls (x<<1)
#define rs (x<<1|1)
#define mid (l+r>>1)
ll mx[N<<2],ad[N<<2];
void pushup(int x){
mx[x]=max(mx[ls],mx[rs]);
}
void pushdown(int x){
ad[ls]+=ad[x];ad[rs]+=ad[x];
mx[ls]+=ad[x];mx[rs]+=ad[x];
ad[x]=0;
}
void build(int x,int l,int r){
mx[x]=0;ad[x]=0;
if(l==r)return ;
build(ls,l,mid);build(rs,mid+1,r);
}
void add(int x,int l,int r,int L,int R,ll p){
if(L>r||l>R)return ;
if(L<=l&&r<=R){
mx[x]+=p;ad[x]+=p;
return ;
}
pushdown(x);
add(ls,l,mid,L,R,p);
add(rs,mid+1,r,L,R,p);
pushup(x);
}
void change(int x,int l,int r,int pos,ll v){
if(pos<l||pos>r)return ;
if(l==r){
mx[x]=max(mx[x],v);
return ;
}
pushdown(x);
change(ls,l,mid,pos,v);
change(rs,mid+1,r,pos,v);
pushup(x);
}
ll query(int x,int l,int r,int L,int R){
if(L>r||l>R)return -inf;
if(L<=l&&r<=R){
return mx[x];
}
pushdown(x);
return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
int n;
struct E{
int x,y,a,b;
}a[N];
bool comp(E A,E B){
if(A.x==B.x)return A.y>B.y;
return A.x<B.x;
}
int len,b[N];
int main(){
while(~scanf("%d",&n)){
len=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
b[++len]=a[i].y;
}
sort(b+1,b+len+1);
len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+len+1,a[i].y)-b,a[i].y++;
len++;
build(1,1,len);
sort(a+1,a+n+1,comp);
for(int i=1;i<=n;i++){
ll tmp=query(1,1,len,1,a[i].y);
change(1,1,len,a[i].y,tmp+a[i].b);
add(1,1,len,a[i].y+1,len,a[i].b);
add(1,1,len,1,a[i].y-1,a[i].a);
}
printf("%lld\n",mx[1]);
}
return 0;
}
J题
Fraction Comparision
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=x; i<y; ++i)
#define mem(x,y) memset(x,y,sizeof(x))
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
#define se second
#define fi first
#define maxn 100005
#define endl '\n'
using namespace std;
ll gcd(ll a ,ll b){
if(b) return gcd(b,a%b);
return a;
}
int main(){
ll x,y,a,b;
while(cin>>x>>a>>y>>b){
if(x*b==y*a) cout<<'='<<endl;
else {
if(x/a>y/b) { cout<<'>'<<endl; continue; }
if(x/a<y/b) { cout<<'<'<<endl; continue; }
x%=a;
y%=b;
if(x*b>y*a) cout<<'>'<<endl;
else cout<<'<'<<endl;
}
}
return 0;
}
京公网安备 11010502036488号