比赛链接
https://ac.nowcoder.com/acm/contest/1110#question
A
样例很友好，把唯一的特殊情况放在样例里头了。
就是-maxlonglong/-1是不能用longlong表示的，需要特判。
PS：该代码本地编译不通过，不知道原因，但提交后能AC。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
样例很友好，把唯一的特殊情况放在样例里头了。
就是-maxlonglong/-1是不能用longlong表示的，需要特判。
PS：该代码本地编译不通过，不知道原因，但提交后能AC。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
ll a,b;
ll solve(){
ll res1=a/b;
// D(a);D(b);D(res1);E;
if(a>=0&&b>0) return res1;
if(a<=0&&b<0) return res1;
if(a%b==0) return res1;
return res1-1;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Simple Arithmetic.in","r",stdin);
while(cin>>a>>b){
if((a==-9223372036854775808) && (b==-1)){
cout<<9223372036854775808<<endl;
continue;
}
cout<<solve()<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
D
类似蓝书上可达性统计那道题，用bitset维护每个点可以到达的点的集合。
算法时间复杂度的重点在于：如果对于每个询问都进行一次拓扑排序，那么时间复杂度与边数有关，本题为稠密图，因此这样写会超时。
仔细观察，可以注意到当遍历完x的所有后继节点后，如果x的颜色为白色，那么x就可以作为他的所有后继节点中白色点，且为合法的路径的起点。
例如对于这组样例
9 10 2
7 1
7 3
1 2
8 9
1 3
2 4
4 3
3 5
3 6
2 3
1
首先从7开始遍历，搜索完5，6，3，7四个点，对答案的贡献分别为0，0，2，3。
然后搜索9，8两个点，对答案的贡献分别为0，1。
之后搜索4，2两个点。从4搜索到3时，因为3已经被访问过了，所以可以直接返回，并对答案产生3的贡献。搜索2的时候同理，只要计算bitset[4]|bitset[2]中的1的数量即可。
即以2号点为起点的合法路径数为4。
于是总的答案就是2+3+1+3+4=13。
两个注意点：
必须要用向量存图，链式前向星会超时。
同时注意遍历x的出边的时候，千万不能写成i<=G[x].size()-1。
因为G[x].size()是无符号数，当G[x].size()=0时，G[x].size()-1会是一个很大的数。
代码如下
/*
类似蓝书上可达性统计那道题，用bitset维护每个点可以到达的点的集合。
算法时间复杂度的重点在于：如果对于每个询问都进行一次拓扑排序，那么时间复杂度与边数有关，本题为稠密图，因此这样写会超时。
仔细观察，可以注意到当遍历完x的所有后继节点后，如果x的颜色为白色，那么x就可以作为他的所有后继节点中白色点，且为合法的路径的起点。
例如对于这组样例
9 10 2
7 1
7 3
1 2
8 9
1 3
2 4
4 3
3 5
3 6
2 3
1
首先从7开始遍历，搜索完5，6，3，7四个点，对答案的贡献分别为0，0，2，3。
然后搜索9，8两个点，对答案的贡献分别为0，1。
之后搜索4，2两个点。从4搜索到3时，因为3已经被访问过了，所以可以直接返回，并对答案产生3的贡献。搜索2的时候同理，只要计算bitset[4]|bitset[2]中的1的数量即可。
即以2号点为起点的合法路径数为4。
于是总的答案就是2+3+1+3+4=13。
两个注意点：
必须要用向量存图，链式前向星会超时。
同时注意遍历x的出边的时候，千万不能写成i<=G[x].size()-1。
因为G[x].size()是无符号数，当G[x].size()=0时，G[x].size()-1会是一个很大的数。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<bitset>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int maxm=maxn*maxn/2;
const int INF=0x3f3f3f3f;
int n,m,Q;
int ans;
int c[maxn]; //颜色 0白 1黑
vector<int>G[maxn];
void init(){
for(int i=1;i<=n;i++) G[i].clear();
memset(c,0,sizeof(c));
}
bitset<maxn+5>s[maxn+5];
int vis[maxn];
void dfs(int x){
if(vis[x]) return;
vis[x]=1;
s[x].reset();
// D(x);D(G[x].size()-1);E;
for(int i=0;i<G[x].size();i++){ //这里千万不能写成i<=G[x].size()-1 因为G[x].size()是无符号数 当G[x].size()=0时 G[x].size()-1会是一个很大的数
int y=G[x][i];
// if(vis[y]) continue;
dfs(y);
if(!c[x]) s[x]|=s[y];
}
if(!c[x]){
// D(x);D(s[x].count()-1);E;
s[x][x]=1; //对于白点 相当于自身可达
ans+=s[x].count()-1; //除去自身
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Dynamic Graph.in","r",stdin);
while(scanf("%d%d%d",&n,&m,&Q)!=EOF){
int from,to;
init();
for(int i=1;i<=m;i++){
scanf("%d%d",&from,&to);
G[from].push_back(to);
}
int p;
while(Q--){
scanf("%d",&p);
c[p]^=1;
memset(vis,0,sizeof(vis));
ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]) dfs(i);
}
printf("%d\n",ans);
}
}
return 0;
}
E
用两个向量记录LIS转移时的所有前后继节点，然后通过n次bfs，来判断当一个点被影响时，后面必然会发生改变的所有点即可。
代码如下
/*
用两个向量记录LIS转移时的所有前后继节点，然后通过n次bfs，来判断当一个点被影响时，后面必然会发生改变的所有点即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
int n;
int f[maxn],a[maxn];
vector<int>v1[maxn],v2[maxn];//v1[i]表示LIS中i的所有前继节点 v2[i]表示LIS中i的所有后继节点
queue<int>q;
int p[maxn]; //p[i]=-1表示被影响到
void init(){
for(int i=1;i<=n;i++) v1[i].clear(),v2[i].clear();
}
void dp(){
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<=i-1;j++) if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
for(int j=1;j<=i-1;j++){
if(a[i]>a[j]){
if(f[i]==f[j]+1){
v1[i].push_back(j);
v2[j].push_back(i);
}
}
}
}
}
void solve(){
for(int i=1;i<=n;i++){
int ans=0;
memset(p,0,sizeof(p));
p[i]=-1;
while(q.size()) q.pop();
q.push(i);
while(q.size()){
int x=q.front();q.pop();
for(int j=0;j<v2[x].size();j++){ //考虑x的所有后继节点y
int y=v2[x][j];
int flag=0;
for(int k=0;k<v1[y].size();k++){ //考虑当前y的所有前继节点z
int z=v1[y][k];
if(p[z]!=-1){
flag=1;
break;
}
}
if(!flag){ //y的所有前继节点都被影响到了。因此只要改变了i，f[y]就一定会变成f[y]-1
p[y]=-1;
q.push(y);
}
}
}
for(int j=1;j<=i-1;j++) ans^=(f[j]*f[j]); //i前面的数不会发生变化
for(int j=i+1;j<=n;j++){
ans^=(f[j]+p[j])*(f[j]+p[j]); //后面的数字可能发生变化（不变或者减一）
}
printf("%d ",ans);
}
printf("\n");
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Longest Increasing Subsequence.in","r",stdin);
while(scanf("%d",&n)!=EOF){
init();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dp();
solve();
}
return 0;
}
L
计算g[n]的时候，预处理一下前缀和和6的逆元即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
ll f[maxn],g[maxn];
int n;
ll a[maxn],a1[maxn],a2[maxn],a3[maxn];
ll inv6;
ll ksm(ll A,ll B,ll p){
ll res=1;
while(B){
if(B&1) res=(res*A)%p;
B>>=1;
A=(A*A)%p;
}
return res;
}
void dp(){
for(int i=3;i<=n;i++){
g[i]=(((((a1[i]*a1[i])%mod*a1[i])%mod-((3*a2[i])%mod*a1[i])%mod+mod)%mod+(2*a3[i])%mod)%mod)*inv6%mod;
if(i>=4){
f[i]=(f[i-1]+(a[i]*g[i-1])%mod)%mod;
}
// D(g[i]);D(f[i]);E;
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Nice Trick.in","r",stdin);
inv6=ksm(6,mod-2,mod);
// D(inv6);E;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a1[i]=(a1[i-1]+a[i])%mod;
a2[i]=(a2[i-1]+a[i]*a[i])%mod;
a3[i]=(a3[i-1]+(a[i]*a[i])%mod*a[i])%mod;
}
dp();
printf("%lld\n",f[n]);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
