A
A应该没啥难的吧直接map<string,map<string,int> >标记 机器ID和文章ID就行
map<string,map<string,int> > mp;
int main()
{
tcase {
string a,b;
cin>>a>>b;
if(mp[a][b]==0) {
mp[a][b]=1;
cout<<"YES"<<endl;
}
else {
cout<<"NO"<<endl;
}
}
return 0;
}
B
直接bfs当前状态看能不能翻转成全是0就行
时间复杂度 O(16162^16)就行
int a[10][10];
void reverse(int x,int y) {
a[x-1][y]=!a[x-1][y];
a[x+1][y]=!a[x+1][y];
a[x][y-1]=!a[x][y-1];
a[x][y+1]=!a[x][y+1];
a[x][y]=!a[x][y];
}
map<ll,int> mp;
int main()
{
closeiostream;
ll x=0,p=1;
for(int i=1;i<=4;i++) {
for(int j=1;j<=4;j++) {
char ch;
cin>>ch;
a[i][j]=ch-'0';
x+=a[i][j]*p;
p*=2;
}
}
queue<ll> que;
mp[x]=1;
que.push(x);
while(!que.empty()) {
if(mp[0]) break;
ll t=que.front();
que.pop();
p=1;
for(int i=1;i<=4;i++) {
for(int j=1;j<=4;j++) {
if(t&p) a[i][j]=1;
else a[i][j]=0;
p*=2;
}
}
for(int i=1;i<=4;i++) {
for(int j=1;j<=4;j++) {
reverse(i,j);
p=1,x=0;
for(int i1=1;i1<=4;i1++) {
for(int j1=1;j1<=4;j1++) {
x+=a[i1][j1]*p;
p*=2;
}
}
reverse(i,j);
if(mp[x]) continue;
mp[x]=1;
que.push(x);
}
}
}
if(mp[0]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
C
从时间复杂度分析那必然是n方的，我们怎样才能n方实现呢？ 先考虑不是两两不能重复的种数为ans="∏_1^4▒∑_1^n▒〖a[i]〗" 在减掉有两两重复的种数不就可以了？ 那怎么实现呢？？？ 我们从四个里面选出来一对两个a,b有重复，另外两个c,d没有，有c(2,4)="6种情况" on枚举a,b的重复项在on枚举c,d的相同个数com,c有而d没有棋的个数cntc, d有而c没有棋的个数cntd, ans-="com这样就行" 减掉贡献就行。 另外还有两对有重复的情况要减掉，a="b,c=d" if(i="=1)" 再考虑有三个有重复而另一个不是的情况有四种情况减去贡献 再考虑有四个有重复的情况有四种情况去贡献即可。
int a[5][5005];
int main()
{
closeiostream;
int n;
cin>>n;
ll ans=1;
for(int i=1;i<=4;i++) {
ll res=0;
for(int j=1;j<=n;j++) {
char ch;
cin>>ch;
a[i][j]=ch-'0';
res+=a[i][j];
}
ans*=res;
}
// 2
for(int i=1;i<=4;i++) {
for(int j=i+1;j<=4;j++) {
for(int k=1;k<=n;k++) {
if(a[i][k] && a[j][k]) {
int p=0,q=0;
for(int x=1;x<=4;x++) {
if(x!=i && x!=j) {
if(p==0) p=x;
else q=x;
}
}
ll cntq=0,cntp=0,com=0;
for(int y=1;y<=n;y++) {
if(y==k) continue;
if(a[q][y] && !a[p][y]) cntq++;
else if(!a[q][y] && a[p][y]) cntp++;
else if(a[q][y] && a[p][y]) com++;
}
ans-=cntq*cntp+(cntq+cntp+com-1)*com;
if(i==1) ans-=com;
}
}
}
}
// 3
for(int i=1;i<=4;i++) {
for(int j=1;j<=n;j++) {
if(!a[i][j]) continue;
for(int k=1;k<=n;k++) {
if(k==j) continue;
int res=0;
for(int x=1;x<=4;x++)
if(x!=i) res+=a[x][k];
if(res==3) ans--;
}
}
}
// 4
for(int i=1;i<=n;i++) {
int res=0;
for(int j=1;j<=4;j++) {
res+=a[j][i];
}
if(res==4) ans--;
}
cout<<ans<<endl;
return 0;
}
D我写崩了，
E
一看树的路径就知道必然是点分治题，用点分治维护路径 dis[v][0]="max(dis[u][0],w);维护路径最大值" dis[v][1]="min(dis[u][1],w);维护路径最小值" 我们得到路径之后不可能去n方计算答案 其实我们可以看到这是一个很清楚的二维偏序问题，我们首先对pair<max,min> a[N]这样的结构最大值升序排序
然后呢？
对于遍历到的a[i]我们知道前面的j<i的点a[j]，最大值都是小于a[i]的,所以对于a[j]来说，如果a[j]的最小值小于a[i]的最小值,贡献等于 a[i].maxa[j].min, 如果a[j]的最小值大于等于a[i]的最小值,贡献等于 a[i].maxa[i].min,用树状数组维护所有的最小值就行，这样就可以logn地得到所有小于a[i].min的a[j],min的和sum了， 还有一点就是要离散化最小值，完毕。代码如下：
#include<bits/stdc++.h>
#define tcase int Case;cin>>Case;while(Case--)
#define closeiostream ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define bug2(a,b) cout<<a<<" "<<b<<endl
#define bug1(a) cout<<a<<endl
#define ll long long
#define PI acos(-1)
#define N 100005
#define P pair<ll,ll>
#define fi first
#define se second
#define makep make_pair
#define ull unsigned long long
//#define endl '\n'
using namespace std;
const ll mod=998244353;
ll c[N][2];
vector<ll> b;
int n,rt,siz[N],maxx[N],dis[N][2];
bool vis[N];
ll a[N];
vector<int> e[N];
int sum;
int id(ll x) {
return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
}
int lowbit(int x) {
return x&(-x);
}
void update(int x,int y,int s) {
for(int i=x;i<=n;i+=lowbit(i))
c[i][s]=(c[i][s]+mod+y)%mod;
}
ll getsum(int x,int s) {
ll ans=0;
for(int i=x;i;i-=lowbit(i))
ans=(ans+c[i][s]+mod)%mod;
return ans;
}
void getrt(int u, int fa) {
siz[u]=1;
maxx[u]=0;
for(auto x:e[u]) {
int v=x;
if(v==fa || vis[v]) continue;
getrt(v,u);
maxx[u]=max(maxx[u],siz[v]);
siz[u]+=siz[v];
}
maxx[u]=max(maxx[u],sum-siz[u]);
if(maxx[u]<maxx[rt]) rt=u;
}
P dd[N],dx[N];
bool cmp(P x,P y) {
return x.fi<y.fi;
}
int cnt,cntz;
void getdis(int u, int fa) {
dd[++cntz].fi=dis[u][0];
dd[cntz].se=dis[u][1];
for(auto x:e[u]) {
int v=x,w=a[x];
if(v==fa || vis[v]) continue;
dis[v][0]=max(dis[u][0],w);
dis[v][1]=min(dis[u][1],w);
getdis(v,u);
}
}
ll ans=0;
void dfz(int u,int fa) {
vis[u]=true;
cnt=0;
dis[u][0]=a[u];
dis[u][1]=a[u];
for(auto x:e[u]) {
int v=x,w=a[x];
if(v==fa || vis[v]) continue;
dis[v][0]=max(dis[u][0],w);
dis[v][1]=min(dis[u][1],w);
cntz=0;
getdis(v,u);
sort(dd+1,dd+1+cntz,cmp);
for(int i=1;i<=cntz;i++) {
ans=(ans+(dd[i].fi*dd[i].se%mod))%mod;
dx[++cnt]=dd[i];
int idx=id(dd[i].se);
ll res=getsum(idx,0),rs=i-getsum(idx,1)-1;
rs=(rs+mod)%mod;
res=(res+mod)%mod;
ans=(ans-res*dd[i].fi%mod+mod)%mod;
ans=(ans-rs*dd[i].se%mod*dd[i].fi%mod+mod)%mod;
update(idx,dd[i].se,0);
update(idx,1,1);
}
for(int i=1;i<=cntz;i++) {
int idx=id(dd[i].se);
update(idx,-dd[i].se,0);
update(idx,-1,1);
}
}
sort(dx+1,dx+1+cnt,cmp);
for(int i=1;i<=cnt;i++) {
int idx=id(dx[i].se);
ll res=getsum(idx,0),rs=i-getsum(idx,1)-1;
rs=(rs+mod)%mod;
res=(res+mod)%mod;
ans=(ans+res*dx[i].fi%mod)%mod;
ans=(ans+rs*dx[i].se%mod*dx[i].fi%mod)%mod;
update(idx,dx[i].se,0);
update(idx,1,1);
}
for(int i=1;i<=cnt;i++) {
int idx=id(dx[i].se);
update(idx,-dx[i].se,0);
update(idx,-1,1);
}
for(auto x:e[u]) {
int v=x;
if(v==fa || vis[v]) continue;
sum=siz[v];
rt=0;
maxx[rt]=INT_MAX;
getrt(v,u);
getrt(rt,-1);
dfz(rt,u);
}
}
void Init_Solve() {
rt=0;
maxx[rt]=INT_MAX;
sum=n;
getrt(1,-1);
getrt(rt,-1);
dfz(rt,-1);
}
int main()
{
closeiostream;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
b.push_back(a[i]);
ans=(ans+a[i]*a[i]%mod)%mod;
}
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
for(int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
Init_Solve();
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号