今天的模拟也太毒瘤了……

 

T1 permutation

　　期望得分：20

　　实际得分：20　　

　　我刚开始是这么想的：T1嘛，应该不会太难，想想正解吧。本来想求出所有不合法的情况，然后用n!减一下。于是用dp，但发现这玩意是有后效性的，硬推了将近一个点儿，最终还是放弃了。只能20分全排列暴力了……

　　正解完全没看懂，居然成了什么二分图的补图，然后还用什么卷积……弃疗了

20分的

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 using namespace std;12 #define enter puts("") 13 #define space putchar(' ')14 #define Mem(a, x) memset(a, x, sizeof(a))15 #define rg register16 typedef long long ll;17 typedef double db;18 const int INF = 0x3f3f3f3f;19 const db eps = 1e-8;20 const int maxn = 12;21 const ll mod = 998244353;22 inline ll read()23 {24 ll ans = 0;25 char ch = getchar(), last = ' ';26 while(!isdigit(ch)) {last = ch; ch = getchar();}27 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}28 if(last == '-') ans = -ans;29 return ans;30 }31 inline void write(ll x)32 {33 if(x < 0) x = -x, putchar('-');34 if(x >= 10) write(x / 10);35 putchar(x % 10 + '0');36 }37 38 int n, k, a[maxn];39 ll ans = 0;40 41 ll fac[maxn * 10000];42 void work0()43 {44 fac[1] = 1;45 for(int i = 2; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;46 write((fac[n] - fac[n - 1]) % mod); enter;47 }48 49 int main()50 {51 freopen("permutation.in", "r", stdin);52 freopen("permutation.out", "w", stdout);53 n = read(); k = read();54 if(n > 10) {work0(); return 0;}55 for(rg int i = 1; i <= n; ++i) a[i] = i;56 do57 {58 bool flg = 1;59 for(rg int i = 1; i <= n; ++i) if(abs(a[i] - i) == k) {flg = 0; break;}60 if(flg) ans++;61 }while(next_permutation(a + 1, a + n + 1));62 write(ans % mod); enter;63 return 0;64 }
               
              
             
            
           
          
         
        
       
      

 

T2 tree

　　期望得分：60

　　实际得分：55

　　60分多好写啊！枚举每一个不在树上的边，删去他然后跑tarjan求桥。丢了5分是因为不在树上的边和树上的边构成了重边，tarjan的时候还要单独判断一下这条边是否是新加的。

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 using namespace std;12 #define enter puts("") 13 #define space putchar(' ')14 #define Mem(a, x) memset(a, x, sizeof(a))15 #define rg register16 typedef long long ll;17 typedef double db;18 const int INF = 0x3f3f3f3f;19 const db eps = 1e-8;20 const int maxn = 3e5 + 5;21 inline ll read()22 {23 ll ans = 0;24 char ch = getchar(), last = ' ';25 while(!isdigit(ch)) {last = ch; ch = getchar();}26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}27 if(last == '-') ans = -ans;28 return ans;29 }30 inline void write(ll x)31 {32 if(x < 0) x = -x, putchar('-');33 if(x >= 10) write(x / 10);34 putchar(x % 10 + '0');35 }36 37 int n, m;38 #define pr pair
                
                 39 #define mp make_pair40 vector
                 
                   v[maxn];41 42 ll ans = 0;43 int dfn[maxn], low[maxn], cnt;44 void tarjan(const int& now, const int& fa, const int& flg)45 {46 dfn[now] = low[now] = ++cnt;47 for(int i = 0; i < (int)v[now].size(); ++i)48 {49 if(v[now][i].second == flg) continue;50 int to = v[now][i].first;51 if(!dfn[to])52 {53 tarjan(to, now, flg);54 low[now] = min(low[now], low[to]);55 if(low[to] > dfn[now]) ans++;56 }57 else if(to != fa || v[now][i].second) low[now] = min(low[now], dfn[to]);58 }59 }60 inline void init()61 {62 for(int i = 1; i <= n; ++i) dfn[i] = low[i] = 0;63 cnt = 0;64 }65 66 int main()67 {68 freopen("tree.in", "r", stdin);69 freopen("tree.out", "w", stdout);70 n = read(); m = read();71 for(int i = 1; i < n; ++i)72 {73 int x = read(), y = read();74 v[x].push_back(mp(y, 0)); v[y].push_back(mp(x, 0));75 }76 for(int i = 1; i <= m; ++i)77 {78 int x = read(), y = read();79 v[x].push_back(mp(y, i)); v[y].push_back(mp(x, i));80 }81 for(int i = 1; i <= m; ++i)82 {83 init();84 for(int j = 1; j <= n; ++j) if(!dfn[j]) tarjan(j, 0, i);85 }86 write(ans); enter;87 return 0;88 }
                 
                
               
              
             
            
           
          
         
        
       
      

　　正解现在看起来也不难：对于新加入的一条边(x, y)，对于原来树上的路径x -> y的所有边而言，必须要割掉这条新的边和自己，才能使整棵树不连通；而如果又有一条边(x, y)，则这些路径上的边怎么割都割不掉了。所以总结一下：新加入一条边(x, y)相当于树上路径加1，最后判断这条边的值：如果是1，对答案的贡献就是1,；如果是0，贡献就是m；否则是0.

　　链上修改可以用树剖，更优的解法是树上差分。时间复杂度取决于lca复杂度。

85分代码（不知为啥有三个点RE了，调了小半个下午没调出来）

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 3e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) last = ch, ch = getchar(); 26 while(isdigit(ch)) ans = ans * 10 + ch - '0', ch = getchar(); 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 void MYFILE() 38 { 39 #ifndef mrclr 40 freopen("tree.in", "r", stdin); 41 freopen("tree.out", "w", stdout); 42 #endif 43 } 44 45 int n, m; 46 struct Edge 47 { 48 int nxt, to; 49 }e[maxn << 2]; 50 int head[maxn], ecnt = 0; 51 void add(int x, int y) 52 { 53 e[++ecnt].to = y; 54 e[ecnt].nxt = head[x]; 55 head[x] = ecnt; 56 } 57 58 int dep[maxn], dp[maxn][28]; 59 void dfs(int now, int fa) 60 { 61 for(int i = 1; i <= 25; ++i) 62 dp[now][i] = dp[dp[now][i - 1]][i - 1]; 63 for(int i = head[now]; i; i = e[i].nxt) 64 { 65 if(e[i].to != fa) 66 { 67 dep[e[i].to] = dep[now] + 1; 68 dp[e[i].to][0] = now; 69 dfs(e[i].to, now); 70 } 71 } 72 } 73 int lca(int x, int y) 74 { 75 if(dep[x] < dep[y]) swap(x, y); 76 for(int i = 25; i >= 0; --i) 77 if(dep[dp[x][i]] >= dep[y]) x = dp[x][i]; 78 if(x == y) return x; 79 for(int i = 25; i >= 0; --i) 80 if(dp[x][i] != dp[y][i]) x = dp[x][i], y = dp[y][i]; 81 return dp[x][0]; 82 } 83 84 int dif[maxn]; 85 void dfs2(int now, int fa) 86 { 87 for(int i = head[now]; i; i = e[i].nxt) 88 { 89 if(e[i].to != fa) 90 { 91 dfs2(e[i].to, now); 92 dif[now] += dif[e[i].to]; 93 } 94 } 95 } 96 97 int main() 98 { 99 MYFILE();100 n = read();101 m = read();102 for(int i = 1; i < n; ++i)103 {104 int x = read(), y = read();105 if(x == y) continue;106 add(x, y); add(y, x);107 }108 dfs(1, 0);109 for(int i = 1; i <= m; ++i)110 {111 int x = read(), y = read();112 dif[x]++; dif[y]++; 113 dif[lca(x, y)] -= 2;114 }115 dfs2(1, 0);116 ll ans = 0;117 for(rg int i = 1; i <= n; ++i)118 {119 ans += (dif[i] == 1);120 ans += (dif[i] == 0) * m;121 }122 write(ans - m); enter;123 return 0;124 }
               
              
             
            
           
          
         
        
       
      

 

 

T3 polynomial

　　期望得分：0

　　实际得分：0

　　模拟能放到T3，那自然不可做。

　　30分手推还是gg了。题解看不懂。

 

明天我觉得应该能考数据结构吧。