第20届上海大学程序设计联赛春季赛（同步赛）

文章目录
- - A. 如何才能穿过传送门（思维）
  - B 逃离魔爪（二维树状数组）
  - C 古老的恩尼格玛机（签到）
  - D 并不智能的卡牌 AI（签到）
  - E 林荫小径（待补）
  - F 到底是多少分啊（待补）
  - G 多吃蘑菇（待补）
  - H 差不多得了（签到）
  - I 数学题真难啊（dp+数学）
A. 如何才能穿过传送门（思维）
思路：往左走是无效的，因此只要考虑一直往右走即可
C o d e : Code: Code:
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl 'n'
#define y1 yyy
typedef long long ll;
typedef pair PII;
const int N=1e6+10,mod=998244353;
int n,m,q,a[N];
int main(){
    cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		a[x]=y;
		a[y]=x;
	}
	for(int i=1;i<=q;i++){
		int k;cin>>k;
		a[k]=-1;
	}
	int ans=0;
	while(++ans){
		if(a[ans]==-1||ans==n+1) break;
		if(a[ans]) ans=a[ans];
	}
	if(ans==n+1)cout<<"YES"< 
B 逃离魔爪（二维树状数组） 
思路：对一块地由1变0、0变1，可以转化为每次对修改时对区间内都+1，如果某块地为偶数就等同于0，奇数就等同于1，而我们最终查询某块矩阵的和的奇偶性，偶数和0等效对奇偶性不产生影响。
 因此可以转化为二维树状数组的区间修改+区间查询模板 

    
     
      
       
        C
       
       
        o
       
       
        d
       
       
        e
       
       
        :
       
      
      
       Code:
      
     
    Code: 
#include 
using namespace std;
#define endl 'n';
#define y1 yyy
typedef long long ll;
typedef unsigned long long u64;
typedef pair PII;
const int N=1e3+10,mod=998244353;
template
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
int n,m,a[N][N],q;
template
struct BIT{
    T c[N][N];
    void modify(int x,int y,T val){
        for(int i=x;i<=n;i+=i&(-i)) {
            for(int j=y;j<=m;j+=j&(-j)){
                c[i][j]+=val;
            }
        }
    }
    T query(int x,int y){
        T s=0;
        for(int i=x;i;i-=i&(-i)) {
            for(int j=y;j;j-=j&(-j)){
                s+=c[i][j];
            }
        }
        return s;
    }
};
BITc11,c12,c21,c22;
void Modify(int x,int y,int val){
    c11.modify(x,y,val);
    c12.modify(x,y,x*val);
    c21.modify(x,y,val*y);
    c22.modify(x,y,x*y*val);
}
ll Ans(int x,int y){
    return c11.query(x,y)*(x+1LL)*(y+1LL)-c12.query(x,y)*(y+1LL)-c21.query(x,y)*(x+1LL)+c22.query(x,y);
}
int main(){
	read(n),read(m),read(q);
	while(q--){
        int op;read(op);
        int x1,y1,x2,y2;
        read(x1),read(y1),read(x2),read(y2);
        if(op==1){
            Modify(x1,y1,1);
            Modify(x1,y2+1,-1);
            Modify(x2+1,y1,-1);
            Modify(x2+1,y2+1,1);
        }else {
            ll ans=Ans(x2,y2)-Ans(x1-1,y2)-Ans(x2,y1-1)+Ans(x1-1,y1-1);
            if(ans%2) puts("1");
            else puts("0");
        }
	}
	return 0;
}
 
C 古老的恩尼格玛机（签到） 
思路：用一个
    
     
      
       
        m
       
       
        a
       
       
        p
       
      
      
       map
      
     
    map存一下下标和字母的关系即可 

    
     
      
       
        C
       
       
        o
       
       
        d
       
       
        e
       
       
        :
       
      
      
       Code:
      
     
    Code: 
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl 'n'
#define y1 yyy
typedef long long ll;
typedef pair PII;
const int N=1e6+10,mod=998244353;
char a[N];
mapmp;
int n;
string s;
int main(){
    for(int i=1;i<=26;i++) cin>>a[i],mp[a[i]]=i;
	cin>>n;
	while(n--){
		cin>>s;
		for(int i=0;i
			if(mp[s[i]]%2==0) cout< 
D 并不智能的卡牌 AI（签到） 
思路：注意特判
    
     
      
       
        m
       
       
        =
       
       
        n
       
       
        =
       
       
        0
       
      
      
       m=n=0
      
     
    m=n=0时答案为
    
     
      
       
        0
       
      
      
       0
      
     
    0 

    
     
      
       
        C
       
       
        o
       
       
        d
       
       
        e
       
       
        :
       
      
      
       Code:
      
     
    Code: 
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl 'n'
#define y1 yyy
typedef long long ll;
typedef pair PII;
const int N=1e6+10,mod=998244353;
ll n,m;
int main(){
    cin>>m>>n;
	if(m==0&&n==0){
		cout<<"0"<
		cout<<"-1"<
		cout< 
E 林荫小径（待补） 
F 到底是多少分啊（待补） 
G 多吃蘑菇（待补） 
H 差不多得了（签到） 
思路：统计有多少个不相邻的
    
     
      
       
        1
       
      
      
       1
      
     
    1 

    
     
      
       
        C
       
       
        o
       
       
        d
       
       
        e
       
       
        ：
       
      
      
       Code：
      
     
    Code： 
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl 'n'
#define y1 yyy
typedef long long ll;
typedef pair PII;
const int N=1e6+10,mod=998244353;
int n,a[N];
void solve(){
    cin>>n;
    int f=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(a[i]==1) f=1;
    }
    if(!f){
        cout<<"0"<
        if(a[i]==1&&a[i-1]!=1) ans++;
    }
    cout<
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
 
I 数学题真难啊（dp+数学） 
思路：显然最后答案是奇数组种类
    
     
      
       
        o
       
       
        d
       
       
        d
       
      
      
       odd
      
     
    odd，偶数组种类
    
     
      
       
        e
       
       
        v
       
       
        e
       
       
        n
       
      
      
       even
      
     
    even：
    
     
      
       
        o
       
       
        d
       
       
        d
       
       
        ∗
       
       
        e
       
       
        v
       
       
        e
       
       
        n
       
      
      
       odd*even
      
     
    odd∗even
 考虑用动态规划，
    
     
      
       
        o
       
       
        d
       
       
        d
       
       
        /
       
       
        e
       
       
        v
       
       
        e
       
       
        n
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       odd/even[i][j]
      
     
    odd/even[i][j]，第一维表示：前
    
     
      
       
        i
       
      
      
       i
      
     
    i个数，第二维表示：在模意义下的前
    
     
      
       
        i
       
      
      
       i
      
     
    i项的和
 因此有转移方程：
    
     
      
       
        d
       
       
        
         p
        
        
         
          i
         
         
          ,
         
         
          k
         
        
       
       
        =
       
       
        
         ∑
        
        
         
          j
         
         
          =
         
         
          0
         
        
        
         9
        
       
       
        
         ∑
        
        
         
          k
         
         
          =
         
         
          0
         
        
        
         
          p
         
         
          −
         
         
          1
         
        
       
       
        d
       
       
        
         p
        
        
         
          i
         
         
          −
         
         
          1
         
         
          ,
         
         
          (
         
         
          k
         
         
          −
         
         
          j
         
         
          %
         
         
          p
         
         
          +
         
         
          p
         
         
          )
         
         
          %
         
         
          p
         
        
       
       
        %
       
       
        m
       
       
        o
       
       
        d
       
       
        (
       
       
        p
       
       
        =
       
       
        3
       
       
        o
       
       
        r
       
       
        9
       
       
        )
       
      
      
       dp_{i,k}=sumlimits_{j=0}^{9}sumlimits_{k=0}^{p-1}dp_{i-1,(k-j%p+p)%p}%mod(p=3or9)
      
     
    dpi,k=j=0∑9k=0∑p−1dpi−1,(k−j%p+p)%p%mod(p=3or9) 

    
     
      
       
        C
       
       
        o
       
       
        d
       
       
        e
       
       
        :
       
      
      
       Code:
      
     
    Code: 
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl 'n'
#define y1 yyy
typedef long long ll;
typedef pair PII;
const int N=1e6+10,mod=998244353;
int n;
ll odd[N][10],even[N][10];
int main(){
    cin>>n;
    odd[0][0]=1,even[0][0]=1;
    for(int i=1;i<=n/2;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<9;k++){
                int u=(k-j%9+9)%9;
                even[i][k]=(even[i][k]+even[i-1][u])%mod;
            }
        }
    }
    for(int i=1;i<=(n+1)/2;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<3;k++){
                int u=(k-j%3+3)%3;
                odd[i][k]=(odd[i][k]+odd[i-1][u])%mod;
            }
        }
    }
    cout<
第20届上海大学程序设计联赛春季赛（同步赛）

C/C++/C#相关栏目本月热门文章
