Educational Codeforces Round 115 (Rated for Div. 2)（D,E)
D
题目给出\(n\)个问题，每个问题都会有一个主题和一个难度，并且没有两个题目的问题和主题都是一样的，我们需要选择\(3\)个问题，满足以下两个条件中的一个
\(1\),三个问题的主题都不一样
\(2\),三个问题的难度都不一样
正难则反
我之前是考虑把这两个条件分开来看，我是找对于主题来说，存在一样的，再计算对于难度来说，存在一样的，但是存在一个问题，就是对于就算是难度有一样的，但是他们的主题是满足条件的，所以我们就不太可能用这样的方法了
然后我们再考虑一下，对于不可能的组合只有两个条件都不满足
那么我们可以对于存在的一个问题，他的主题是\(u\),难度是\(v\),那么我们还要选择两个，一个数主题还是为\(u\)的，一个选择难度还是\(v\)的（题目说了没有两个题目的问题和主题都是一样的，所以这次选择的一定不会存在重叠的，只能是\((u,v) (u,x) (y,v)\)这三个）
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,t;
int a[maxn],b[maxn];
void solve()
{
cin>>n;
int ans=0;
vector<vector<int>>x(n+1),y(n+1);
for (int i=1;i<=n;i++)
{
int u,v;
cin>>u>>v;
x[u].push_back(v);
y[v].push_back(u);
}
ans=n*(n-1)*(n-2)/6;
for (int u=1;u<=n;u++)
{
for (auto v:x[u])
{
int cnt1=x[u].size()-1;
int cnt2=y[v].size()-1;
ans-=cnt1*cnt2;
}
}
cout<<ans<<"\n";
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
E
这个题目大意就是有一个网格，每一个格子可以是自由的，也可以是有限制的，我们可以用这些自由的格子组成阶梯，然后我们会有\(k\)次询问，每次都会选择一个位置的状态进行翻转，问翻转后此时可以组成多少个阶梯
对于阶梯的组成，有两种方式，如下
还有另外一种组成方式
然后，我们对于每一个位置，它可以有两种身份，\(0\)代表的是以第一种方式到达这个位置的，\(1\)代表的是以第二种方式到达这个位置的
那么我们可以用\(dp[i] [j] [0]\)和\(dp[i] [j] [1]\),然后还可以得出状态转移方程
dp[i][j][0]=dp[i-1][j][1]+1;
dp[i][j][1]=dp[i][j-1][0]+1;
这是一开始没有带限制的格子的状态
然后对于每一次翻转，依情况而定
那么对于把带限制的格子变成呢过没有限制的格子
那么我们对于那些\((x,y)\)
那么我们就让\(f[x] [y] [1]=f[x-1] [y] [0]+1\)和\(f[x] [y] [0]=f[x] [y-1] [1]+1\)
多出了这一个位置不仅影响了它自己这个位置，还影响了它后面的位置（可以到达）
然后我们就直接模拟从\((x,y)\)到达后面的这些位置（连续不可断），后面到达的都要加上\((x,y)\)之前的相应的路径的数量，记得两种组成方式都要模拟
然后对于那些把自由的格子变成带限制的格子，需要减
把这一个位置的\(f[x] [y] [1]=0\)和\(f[x] [y] [0]=0\)
然后对于那些可以影响了它后面的位置也要减
也是模拟，减去它该减去的数量
每次记录此时的答案，还有那些的变化，这样就可以直接得到答案了
具体的就看代码吧
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
#define int long long
const int maxn=1e3+10;
int n,t,m,q;
int sum;
int f[maxn][maxn][2];
void solve()
{
int x,y;
cin>>x>>y;
if(f[x][y][0])
{
int a=f[x][y][0],b=f[x][y][1];
f[x][y][0]=f[x][y][1]=0;
sum-=a+b-1;
for (int i=x,j=y+1,flag=1;i<=n&&j<=m;flag^=1)//x,y作为0可到达的位置都要减去x,y作为0对那个位置的贡献
{
if(flag&&f[i][j][1])//还要可到达，f[i][j][1]不为0
{
f[i][j][1]-=a;
}
else if(!flag&&f[i][j][0])
{
f[i][j][0]-=a;
}
else break;
sum-=a;
if(flag)i++;//找下一个位置
else j++;
}
for (int i=x+1,j=y,flag=1;i<=n&&j<=m;flag^=1)
{
if(flag&&f[i][j][0])
{
f[i][j][0]-=b;
}
else if(!flag&&f[i][j][1])
{
f[i][j][1]-=b;
}
else break;
sum-=b;
if(flag)j++;
else i++;
}
}
else
{
int a=f[x-1][y][1]+1;
int b=f[x][y-1][0]+1;
f[x][y][0]=a;
f[x][y][1]=b;
sum+=a+b-1;
for (int i=x,j=y+1,flag=1;i<=n&&j<=m;flag^=1)//同样是模拟，不过这次的影响是加
{
if(flag&&f[i][j][1])
{
f[i][j][1]+=a;
}
else if(!flag&&f[i][j][0])
{
f[i][j][0]+=a;
}
else break;
sum+=a;
if(flag)i++;
else j++;
}
for (int i=x+1,j=y,flag=1;i<=n&&j<=m;flag^=1)
{
if(flag&&f[i][j][0])
{
f[i][j][0]+=b;
}
else if(!flag&&f[i][j][1])
{
f[i][j][1]+=b;
}
else break;
sum+=b;
if(flag)j++;
else i++;
}
}
cout<<sum<<"\n";
return ;
}
signed main ()
{
cin>>n>>m>>q;
sum=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
f[i][j][0]=f[i-1][j][1]+1;
f[i][j][1]=f[i][j-1][0]+1;
sum+=f[i][j][0]+f[i][j][1]-1;//有重叠部分，当只有单独一个格子的时候，它既是1，也是0
}
}
while (q--)
{
solve();
}
system ("pause");
return 0;
}