T1：Language
注意到单词长度是无限的这个条件，分类讨论它的循环节"PIG" "IGP" "GPI"
将要操作的单词的每一位分别与三个循环节作比较，用前缀和维护其每一个子串需要修改的次数，取最小值即可
AC CODE
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,k,prep[200009],minn; 4 string a; 5 6 void count(string s){ 7 int p=0; 8 for(int i=1;i<=n;i++){ 9 prep[i]=prep[i-1]; 10 if(a[i]!=s[p])prep[i]++; 11 if(p==2)p=0; 12 else p++; 13 } 14 for(int i=k;i<=n;i++) 15 minn=min(minn,prep[i]-prep[i-k]); 16 } 17 18 void solve(){ 19 minn=114514; 20 cin>>n>>k>>a; 21 a=' '+a; 22 count("PIG"); 23 count("IGP"); 24 count("GPI"); 25 cout<<minn<<"\n"; 26 } 27 28 int main() { 29 freopen("A.in","r",stdin); 30 freopen("A.out","w",stdout); 31 prep[0]=0; 32 int T; 33 cin>>T; 34 while(T--)solve(); 35 return 0; 36 }
T2：Seat
“大胆猜测，小心求证”
观察到两个样例的n都是奇数，由此可以大胆地猜测当n为偶数时无解
那么如何证明呢？
当找不到规律时，我们可以把样例中规模较大而便于计算的样例拿去手算
选择样例2进行手算，过程如下：
很显然，此过程中，是两组两组的编号进行操作的，我们将此定义为一组操作。
我们还发现当一个编号被移动到目标位置（即其正对面的位置）以后，不再被操作（处0以外）。
因此，每一组操作具有独立性，即每一组操作之间互不影响。
那么显而易见，对于每一组操作，假设现在需要交换的两组为(a,a')和(b,b')，坐在空位对面的人为x，则操作顺序[a',a,x,a',b',x,b',a',x,b',b']一定可以交换这两组，然后分组交换最后判断空位的位置是否需要再交换一次即可。
那么很明显，当n为偶数时，总会有一组操作无法组成两组编号加上一个空位（奇偶性），也就意味着无法进行上述操作，故当n为偶数时无解，直接输出"-1"即可
AC CODE
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 2e5 + 5; 4 int n,m,a[N]; 5 int main(){ 6 freopen("B.in","r",stdin); 7 freopen("B.out","w",stdout); 8 scanf("%d",&n); 9 for(int i = 0; i <= 2 * n - 1; i++) scanf("%d",&a[i]); 10 int pos = 0; 11 for(int i = 0; i <= 2 * n - 1; i++){ 12 if(a[i] == 0) pos = i; 13 } 14 if(n % 2 == 0){ 15 puts("-1"); 16 return 0; 17 } 18 printf("%d\n", (n / 2) * 11 + ((n - 1) % 4 == 0)); 19 bool flag = 0; 20 for(int i = 0; i <n ; i++){ 21 22 if(a[i] != 0 && a[i + n] != 0){ 23 int j = i + 1; 24 if(a[j] == 0 || a[j + n] == 0) j++; 25 if(pos < n){ 26 printf("%d ",a[i + n]); 27 printf("%d ",a[i]); 28 printf("%d ",a[(pos + n) % (2 * n)]); 29 printf("%d ",a[i + n]); 30 printf("%d ",a[j + n]); 31 printf("%d ",a[(pos + n) % (2 * n)]); 32 printf("%d ",a[i + n]); 33 printf("%d ",a[j + n]); 34 printf("%d ",a[(pos + n) % (2 * n)]); 35 printf("%d ",a[j]); 36 printf("%d ",a[j + n]); 37 } 38 else{ 39 printf("%d ",a[i]); 40 printf("%d ",a[i + n]); 41 printf("%d ",a[(pos + n) % (2 * n)]); 42 printf("%d ",a[i]); 43 printf("%d ",a[j]); 44 printf("%d ",a[(pos + n) % (2 * n)]); 45 printf("%d ",a[i]); 46 printf("%d ",a[j]); 47 printf("%d ",a[(pos + n) % (2 * n)]); 48 printf("%d ",a[j + n]); 49 printf("%d ",a[j]); 50 } 51 swap(a[pos],a[(pos + n) % (2 * n)]); 52 pos = (pos + n) % (2 * n); 53 i = j; 54 flag^=1; 55 } 56 else continue; 57 } 58 if(!flag) printf("%d ",a[(pos + n) % (2 * n)]); 59 return 0; 60 }
T3:Travel
考虑Dijkstra算法的流程。
如果我们将所有点同时当作起点放入单调队列中，并分别维护从每个点出发的最短路，前k个从队列中弹出的点对即为所求答案。
但是如果对于每个弹出的(s,t)点对，更新其所有边可能导致k的代价。
考虑这样一种情况，假设链接点t按照边权从小到大排序，et(i)为与点t相连的权值第i大的边，在(s,t)+et(i)弹出单调队列前，(s,t)+et(i+1)一定不会成为答案。
故我们对于每个弹出队列的点对(s,t)+et(i),只需更新其相连的权值最小的边与(s,t)+et(i+1)即可。
时间复杂度O(N+K)log(N+K)+MlogM)。
AC CODE
1 #pragma GCC optimize ("O3") 2 #pragma GCC target ("sse4") 3 #include <bits/stdc++.h> 4 #include <ext/pb_ds/tree_policy.hpp> 5 #include <ext/pb_ds/assoc_container.hpp> 6 using namespace std; 7 using namespace __gnu_pbds; 8 typedef long long ll; 9 typedef long double ld; 10 typedef complex<ld> cd; 11 typedef pair<int, int> pi; 12 typedef pair<ll,ll> pl; 13 typedef pair<ld,ld> pd; 14 typedef vector<int> vi; 15 typedef vector<ld> vd; 16 typedef vector<ll> vl; 17 typedef vector<pi> vpi; 18 typedef vector<pl> vpl; 19 typedef vector<cd> vcd; 20 template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; 21 #define FOR(i, a, b) for (int i=a; i<(b); i++) 22 #define F0R(i, a) for (int i=0; i<(a); i++) 23 #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) 24 #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) 25 #define sz(x) (int)(x).size() 26 #define mp make_pair 27 #define pb push_back 28 #define f first 29 #define s second 30 #define lb lower_bound 31 #define ub upper_bound 32 #define all(x) x.begin(), x.end() 33 #define shandom_ruffle random_shuffle 34 const int MOD = 1e9+7; 35 const ll INF = 1e18; 36 const int MX = 1e5+1; //check the limits, dummy 37 ll ans = 0; 38 struct data { 39 ll weight; int start, last, index; 40 data(ll w, int S, int L, int I) {weight = w; start = S; last = L; index = I;} 41 bool operator<(data other) const{return weight > other.weight;} 42 }; 43 int main() { 44 ios_base::sync_with_stdio(0); cin.tie(0); 45 int N, M, K; cin >> N >> M >> K; 46 vector<vpl> graph(N); 47 F0R(i, M) { 48 ll A, B, C; cin >> A >> B >> C; A--; B--; 49 graph[A].pb(mp(C, B)); 50 graph[B].pb(mp(C, A)); 51 } 52 F0R(i, N)sort(all(graph[i])); 53 priority_queue<data> pq; 54 K *= 2; 55 set<pl> visited; 56 F0R(i, N) {pq.push(data(graph[i][0].f, i, i, 0));visited.insert(mp(i, i));} 57 while (!pq.empty()) { 58 data cur = pq.top(); 59 pq.pop(); 60 int nxt = graph[cur.last][cur.index].s; 61 if (!visited.count(mp(cur.start, graph[cur.last][cur.index].s))) { 62 visited.insert(mp(cur.start, graph[cur.last][cur.index].s)); 63 K--; 64 ans += cur.weight; 65 if(K == 0) {cout << ans << endl; return 0;} 66 pq.push(data(cur.weight + graph[nxt][0].f, cur.start, nxt, 0)); 67 } 68 if (cur.index + 1 < sz(graph[cur.last])) 69 pq.push(data(cur.weight - graph[cur.last][cur.index].f + graph[cur.last][cur.index + 1].f, cur.start, cur.last, cur.index + 1)); 70 } 71 return 0; 72 }
前面那一大堆纯属装X的，不是吗？（滑稽）
T4:Nobel
As the saying goes , easier said than done...
首先意识到碰撞只会在相邻的粒子之间发生，一共三种情况：同时向左，同时向右，相向运动，每种情况的碰撞时间可以O(1)求出。我
们对于所有碰撞情况按照时间排序，只要求出每种碰撞为第一次碰撞的概率即可(也就是前i-1种碰撞全不发生减掉前种碰撞全不发生的概率)
每种粒子和他上一个粒子子互相作用的情况可以用2*2矩阵表示，累乘即可得到前i种全不发生的概率，用线段树维护矩阵即可。
AC CODE
1 #include<bits/stdc++.h> 2 #define re register 3 #define inc(i,j,k) for(re int i=j;i<=k;i++) 4 #define ll long long 5 #define lc o<<1 6 #define rc o<<1|1 7 using namespace std; 8 const int mod=998244353; 9 const int N=2e5+5; 10 inline int read(){ 11 int x=0,f=1; 12 char ch=getchar(); 13 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar(); 15 return f*x; 16 } 17 int n,x[N],v[N],tot; 18 ll p[N],inv,ans; 19 ll qp(ll x,ll k){ 20 ll res=1; 21 while(k){ 22 if(k&1) res=res*x%mod; 23 k>>=1,x=x*x%mod; 24 } 25 return res; 26 } 27 struct mat{ 28 ll m[2][2]; 29 void clear(){memset(m,0,sizeof(m));} 30 }t[N<<2],a[N]; 31 mat operator*(mat a,mat b){ 32 mat tmp;tmp.clear(); 33 inc(i,0,1) 34 inc(j,0,1) 35 inc(k,0,1) (tmp.m[i][j]+=a.m[i][k]*b.m[k][j]%mod)%=mod; 36 return tmp; 37 } 38 struct opt{ 39 int u,v,pu,pv; 40 ll dx,dv; 41 opt(){} 42 opt(int uu,int vv,int p_u,int p_v,int d_x,int d_v){u=uu,v=vv,pu=p_u,pv=p_v,dx=d_x,dv=d_v;} 43 }P[N<<2]; 44 bool operator<(opt x,opt y){return x.dx*y.dv<y.dx*x.dv;} 45 void ins(int o,int l,int r,int x){ 46 if(l==r){t[o]=a[l];return;} 47 int mid=(l+r)>>1; 48 if(x<=mid) ins(lc,l,mid,x); 49 else ins(rc,mid+1,r,x); 50 t[o]=t[lc]*t[rc]; 51 } 52 mat query(int o,int l,int r,int x,int y){ 53 if(x<=l&&r<=y) return t[o]; 54 int mid=(l+r)>>1; 55 if(x>mid) return query(rc,mid+1,r,x,y); 56 if(y<=mid) return query(lc,l,mid,x,y); 57 return query(lc,l,mid,x,y)*query(rc,mid+1,r,x,y); 58 } 59 int main(){ 60 inv=qp(100,mod-2); 61 n=read(); 62 inc(i,1,n){ 63 x[i]=read(),v[i]=read(),p[i]=read(); 64 p[i]=p[i]*inv%mod;p[i]=(1-p[i]+mod)%mod; 65 if(i==1){ 66 a[i].m[0][0]=p[i]; 67 a[i].m[0][1]=(1-p[i]+mod)%mod; 68 ins(1,1,n,i); 69 } 70 else{ 71 a[i].m[0][0]=a[i].m[1][0]=p[i]; 72 a[i].m[0][1]=a[i].m[1][1]=(1-p[i]+mod)%mod; 73 ins(1,1,n,i); 74 if(v[i]-v[i-1]>0) P[++tot]=opt(i-1,i,0,0,x[i]-x[i-1],v[i]-v[i-1]); 75 if(v[i-1]-v[i]>0) P[++tot]=opt(i-1,i,1,1,x[i]-x[i-1],v[i-1]-v[i]); 76 if(v[i-1]+v[i]>0) P[++tot]=opt(i-1,i,1,0,x[i]-x[i-1],v[i-1]+v[i]); 77 } 78 } 79 sort(P+1,P+1+tot); 80 inc(i,1,tot){ 81 int l=P[i].u,r=P[i].v; 82 ll ret=P[i].dx*qp(P[i].dv,mod-2)%mod; 83 mat tmp; 84 tmp=query(1,1,n,1,l); 85 ret=ret*(tmp.m[0][P[i].pu]+tmp.m[1][P[i].pu])%mod; 86 ret=ret*a[r].m[P[i].pu][P[i].pv]%mod; 87 if(r!=n){ 88 tmp=query(1,1,n,r+1,n); 89 ret=ret*(tmp.m[P[i].pv][0]+tmp.m[P[i].pv][1])%mod; 90 } 91 (ans+=ret)%=mod; 92 a[r].m[P[i].pu][P[i].pv]=0; 93 ins(1,1,n,r); 94 } 95 printf("%lld",ans); 96 }
归（做）纳（题）与（的）总（心）结（得）
T1:半小时就切了好吧O(∩_∩)O
T2:找到规律就好做啦~(ง •_•)ง
T3:亿点点小难哦~（＞人＜；）
T4:整个人都麻了好吧( ఠൠఠ )ﾉ
终于又水了一篇喽，溜了溜了ε=ε=ε=(~￣▽￣)~