預計分數：100+60+0=160
實際分數：100+80+0=180
T1
題目描述
現在有一個字符串，每個字母出現的次數均為偶數。接下來我們把第一次出現的字母a和第二次出現的a連一條線，第三次出現的和四次出現的字母a連一條線，第五次出現的和六次出現的字母a連一條線...對其他25個字母也做同樣的操作。
現在我們想知道有多少對連線交叉。交叉的定義為一個連線的端點在另外一個連線的內部，另外一個端點在外部。
下圖是一個例子，共有三對連線交叉（我們連線的時候，只能從字符串上方經過）。
輸入格式
一行一個字符串。保證字符串均由小寫字母組成，且每個字母出現次數為偶數次。
輸出格式
一個整數，表示答案。
樣例輸入
abaazooabz
樣例輸出
3
數據范圍
對于30% 的數據，字符串長度不超過50。
對于100% 的數據，字符串長度不超過100,000。
?
正解的做法我一開始想到了
但是我感覺時間復雜度應該是O(n^2)，于是就沒有寫
然后自己推了一個很刁鉆的做法
首先把每一個節點按照題目的規則，從左到右依次編號
把相同編號的兩個點的位置看做一條線段
開一棵線段樹
每次查詢左端點的權值-右端點的權值，加到答案里
再在線段樹中把當前節點的左右端點之間的權值+1
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define ls k<<1 6 #define rs k<<1|1 7 using namespace std; 8 const int MAXN=1000004; 9 inline int read() 10 { 11 char c=getchar();int x=0,f=1; 12 while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} 13 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f; 14 } 15 struct node 16 { 17 int l,r,w,f; 18 }tree[MAXN]; 19 char s[MAXN]; 20 int nxt[MAXN]; 21 int pre[MAXN]; 22 int vis[MAXN]; 23 int ans=0; 24 inline void update(int k) 25 { 26 tree[k].w=tree[ls].w+tree[rs].w; 27 } 28 inline void down(int k) 29 { 30 tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].f; 31 tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].f; 32 tree[ls].f+=tree[k].f; 33 tree[rs].f+=tree[k].f; 34 tree[k].f=0; 35 } 36 inline void Build_Tree(int ll,int rr,int k) 37 { 38 tree[k].l=ll;tree[k].r=rr; 39 if(tree[k].l==tree[k].r){ tree[k].w=0;return ; } 40 int mid=tree[k].l+tree[k].r>>1; 41 Build_Tree(ll,mid,ls);Build_Tree(mid+1,rr,rs); 42 update(k); 43 } 44 inline void Point_Ask(int pos,int k) 45 { 46 if(tree[k].l==tree[k].r) 47 { 48 ans=tree[k].w; 49 return ; 50 } 51 if(tree[k].f) down(k); 52 int mid=tree[k].l+tree[k].r>>1; 53 if(pos<=mid) Point_Ask(pos,ls); 54 else Point_Ask(pos,rs); 55 update(k); 56 } 57 inline void Interval_Add(int ll,int rr,int val,int k) 58 { 59 if(ll<=tree[k].l&&tree[k].r<=rr) 60 { 61 tree[k].w+=(tree[k].r-tree[k].l+1)*val; 62 tree[k].f+=val; 63 return ; 64 } 65 if(tree[k].f) down(k); 66 int mid=tree[k].l+tree[k].r>>1; 67 if(ll<=mid) Interval_Add(ll,rr,val,ls); 68 if(rr>mid) Interval_Add(ll,rr,val,rs); 69 update(k); 70 } 71 int main() 72 { 73 freopen("cross.in","r",stdin); 74 freopen("cross.out","w",stdout); 75 scanf("%s",s+1); 76 int n=strlen(s+1); 77 Build_Tree(1,n,1); 78 for(int i=1;i<=n;i++) 79 { 80 if(pre[s[i]]==0) pre[s[i]]=i; 81 if(pre[s[i]]) nxt[pre[s[i]]]=i,pre[s[i]]=i; 82 } 83 long long int tot=0; 84 for(int i=1;i<=n;i++) 85 { 86 if(vis[i]==1) continue; 87 Point_Ask(i,1);int p=ans; 88 Point_Ask(nxt[i],1); 89 tot=tot+p-ans; 90 Interval_Add(i,nxt[i],1,1); 91 vis[i]=vis[nxt[i]]=1; 92 } 93 printf("%lld",tot); 94 return 0; 95 }
?
T2跳跳虎回家
英?名稱: move
時間限制: 1s
空間限制: 256M
題?描述
跳跳虎在外?出去玩忘了時間，現在他需要在最短的時間內趕回家。
跳跳虎所在的世界可以抽象成?個含有 個點的圖（點編號從 到 ），跳跳虎現在在 號點，跳跳虎的家在 號點。
圖上?共有 條單向邊，通過每條邊有固定的時間花費。
同時，還存在若?個單向傳送通道，傳送通道也有其時間花費。
傳送通道?般來說?普通的道路更快，但是跳跳虎最多只能使? 次。
跳跳虎想知道他回到家的最?時間消耗是多少。
輸?格式
第??輸? 個整數 （ 表?點數， 表?普通道路的數量， 表?傳送通道的數量， 表?跳跳虎最多使? 次傳送通道）
接下來 ?每? 個整數 ，表?有?條從 到 ，時間花費為 的普通道路( )
接下來 ?每? 個整數 ，表?有?條從 到 ，時間花費為 的傳送通道( )
輸出格式
輸出???個整數表?最?時間消耗，如果沒法回到家輸出 。
樣例輸?
5 5 2 1
1 2 1
1 3 2
2 4 2
3 4 3
4 5 4
1 4 1
2 5 1
樣例輸出
2
數據范圍和約定
對于 的數據，
對于另外 的數據，
對于 的數據，
n 1 n 1 n
m
k
4 n,m,q,k n m q k k
m 3 u,v,w u v w 1 ≤ u,v ≤ n,1 ≤ w ≤ 10 3
q 3 x,y,z x y z 1 ≤ x,y ≤ n,1 ≤ z ≤ 10 3
?1
30% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k = 0
30% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k = 1
100% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,0 ≤ k ≤ 10
?
直接跑最短路——》30分
枚舉走哪一條邊——》30分
無視最后的條件跑最短路——》40分
數據太水了沒辦法。。。。。。
?
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=8004; 8 const int INF=0x7fffff; 9 inline int read() 10 { 11 char c=getchar();int x=0,f=1; 12 while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} 13 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f; 14 } 15 int n,m,q,k; 16 int dis[MAXN]; 17 int vis[MAXN]; 18 struct node 19 { 20 int u,v,w,nxt; 21 }edge[MAXN]; 22 int head[MAXN]; 23 int num=1; 24 inline void add_edge(int x,int y,int z) 25 { 26 edge[num].u=x; 27 edge[num].v=y; 28 edge[num].w=z; 29 edge[num].nxt=head[x]; 30 head[x]=num++; 31 } 32 struct node2 33 { 34 int u,v,w,nxt; 35 }edge2[MAXN]; 36 int head2[MAXN]; 37 int num2=1; 38 inline void add_edge2(int x,int y,int z) 39 { 40 edge2[num2].u=x; 41 edge2[num2].v=y; 42 edge2[num2].w=z; 43 edge2[num2].nxt=head2[x]; 44 head2[x]=num2++; 45 } 46 int SPFA(int S,int T) 47 { 48 for(int i=1;i<=n;i++) dis[i]=INF; 49 dis[S]=0; 50 queue<int>q;q.push(S); 51 while(q.size()!=0) 52 { 53 int p=q.front();q.pop(); 54 vis[p]=0; 55 for(int i=head[p];i!=-1;i=edge[i].nxt) 56 { 57 if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w) 58 { 59 dis[edge[i].v]=dis[edge[i].u]+edge[i].w; 60 if(vis[edge[i].v]==0) 61 { 62 q.push(edge[i].v); 63 vis[edge[i].v]=1; 64 } 65 } 66 } 67 } 68 return dis[n]; 69 } 70 int dp[501][4001]; 71 int rudu[501]; 72 inline void Topsort() 73 { 74 queue<int>q; 75 for(int i=1;i<=500;i++) 76 for(int j=1;j<=4000;j++) dp[i][j]=INF; 77 for(int i=1;i<=n;i++) 78 if(rudu[i]==0) q.push(i),dp[i][0]=0; 79 80 while(q.size()!=0) 81 { 82 int p=q.front();q.pop(); 83 for(int i=head[p];i!=-1;i=edge[i].nxt) 84 for(int j=0;j<=k;j++) 85 { 86 dp[edge[i].v][j]=min(dp[edge[i].v][j],dp[i][j]+edge[i].w); 87 rudu[edge[i].v]--; 88 if(rudu[edge[i].v]==0) q.push(edge[i].v); 89 } 90 91 for(int i=head2[p];i!=-1;i=edge2[i].nxt) 92 for(int j=1;j<=k;j++) 93 { 94 dp[edge[i].v][j]=min(dp[edge[i].v][j],dp[i][j-1]+edge[i].w); 95 if(rudu[edge[i].v]==0) q.push(edge[i].v); 96 } 97 98 } 99 printf("%d",dp[n][0]); 100 } 101 int main() 102 { 103 freopen("move.in","r",stdin); 104 freopen("move.out","w",stdout); 105 n=read(),m=read(),q=read(),k=read(); 106 memset(head,-1,sizeof(head)); 107 memset(head2,-1,sizeof(head2)); 108 if(k>=q) 109 { 110 for(int i=1;i<=m+q;i++) 111 { 112 int x=read(),y=read(),z=read(); 113 add_edge(x,y,z); 114 } 115 int p=SPFA(1,n); 116 if(p==INF) printf("-1"); 117 else printf("%d",p); 118 } 119 else 120 { 121 for(int i=1;i<=m;i++) 122 { 123 int x=read(),y=read(),z=read(); 124 add_edge(x,y,z);rudu[y]++; 125 } 126 for(int i=1;i<=q;i++) 127 { 128 int x=read(),y=read(),z=read(); 129 add_edge2(x,y,z);rudu[y]++; 130 } 131 if(k==0)//一條通道都不能選 132 { 133 int p=SPFA(1,n); 134 if(p==INF) printf("-1"); 135 else printf("%d",p); 136 } 137 else if(k==1) 138 { 139 int ans=INF; 140 for(int i=1;i<=num2-1;i++)//枚舉選擇那一條邊 141 { 142 add_edge(edge2[i].u,edge2[i].v,edge2[i].w); 143 int p=SPFA(1,n); 144 if(p!=INF) ans=min(ans,p); 145 num--; 146 head[edge2[i].u]=edge[head[edge2[i].u]].nxt; 147 } 148 printf("%d",ans); 149 } 150 else 151 { 152 Topsort(); 153 } 154 } 155 156 return 0; 157 }
?
?
T3秀秀 和哺 嚕國 （ cut?
時間限制：
1s空間限制：512MB
【問題描述】
哺嚕國里有!個城市，有的城市之間有高速公路相連。在最開始時，哺嚕國里有! ? 1條高
速公路，且任意兩座城市之間都存在一條由高速公路組成的通路。
由于高速公路的維護成本很高， 為了減少哺嚕國的財政支出， 將更多的錢用來哺育小哺嚕，
秀秀女王決定關閉一些高速公路。 但是為了保證哺嚕國居民的正常生活， 不能關閉太多的高速
公路，要保證每個城市可以通過高速公路與至少$個城市（包括自己）相連。
在得到了秀秀女王的指令后，交通部長華華決定先進行預調研。華華想知道在滿足每個城
市都可以與至少$個城市相連的前提下，有多少種關閉高速公路的方案（可以一條也不關） 。兩
種方案不同， 當且僅當存在一條高速公路在一個方案中被關閉， 而在另外一個方案中沒有被關
閉。
由于方案數可能很大， 你只需輸出不同方案數對786433取模后的結果即可。 其中786433 =
6×2 -. + 1。
【輸入格式】
從文件 cut.in 中讀入數據。
輸入第一行，包含兩個正整數!,$。
接下來的! ? 1行，每行包含兩個正整數1和2，表示城市1和城市2之間有一條高速公路相
連。
【輸出格式】
輸出文件到 cut.out 中。
輸出一個非負整數，表示所求方案數對 786433 取模后的結果。
【樣例 1 輸入】
5 2
1 2
2 3
3 4
4 5
【樣例 1 輸出】
3
【樣例 1 解釋】
三種方案分別為：
一條高速公路也不關閉；
關閉城市 2 和城市 3 之間的高速公路；
關閉城市 3 和城市 4 之間的高速公路。
【樣例 2 輸入】
10 2
1 2
1 3
2 4
2 5
3 6
3 7
3 10
5 8
6 9
【樣例 2 輸出】
12
【子任務】
對于20%的數據：! ≤ 20;
另有30%的數據：! ≤ 100;
另有10%的數據：$ ≤ 100;
另有20%的數據：! ≤ 1000;
對于100%的數據：! ≤ 5000,$ ≤ !。
?
不會做，
寫了個2^n的還被卡了
正解：
考慮用樹形??來解決這道問題。
設?[?][?] 表示在?的子樹中?所在的連通塊大小為?，且其他連通塊大小均符合要求的刪邊方案數
對于每個點?我們一棵一棵地將其子樹加進來，設新加入子樹的根為?
若刪除?與?之間的邊，則用?[?][?] * sum(?[?][?]) s \in [k,n] 去更新?[?][?]
若不刪?與?之間的邊，則枚舉?所在連通塊的大小?，并更新?[?][?+?]
時間復雜度 O(?^3) ？
考慮一個優化：每次新加一顆子樹時，?只需枚舉到前面已經加進來的子樹大小之和，?也只需枚舉到新子樹的大小
這只是一個常數優化？其實每個點對相當于只在???處被算了一次
故優化后的時間復雜度是O（?^2)的,本題得以解決。
?
總結：
這次考得還算可以吧，該拿的分都拿到了
但是這次考試的區分度不是很大
智商性選手比較吃虧，RP行選手比較占優233333
?
