362-c 题给了N个（L,R）数据对，求X1-XN满足和为0，而且Li<=Xi<=Ri，先读入数据，分别求所有下边界和上边界的和，很明显如果下边界之和大于0或者上边界之和小于0，答案是不可能存在的输出-1。我想到了这道题是贪心但是没想到具体解法，hh，看了题解，把题目想成向坑里面注水，坑里面的初始水量就设成下边界Li，剩下要填的水量差值即diff=0-下边界之后，再遍历每个水坑，第i个水坑最多再注入Ri-Li升水，每个水坑现有水量更新成原有水量叫上差值和最大注水量的最小值，更新差值，如果差值变为0，条件满足了，跳出循环，输出每个水坑的水量。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;int main()
{int n;cin>>n;vector<pii> vec(n+1);vector<ll> sl(n+1),sr(n+1),ans(n+1);ll s1=0,s2=0;for(int i=1;i<=n;++i){cin>>vec[i].first>>vec[i].second;s1+=vec[i].first,s2+=vec[i].second;sl[i]=sl[i-1]+vec[i].first,sr[i]=sr[i-1]+vec[i].second;ans[i]=vec[i].first;}if(s1>0||s2<0){cout<<"No";return 0;}cout<<"Yes\n";ll diff=0-s1;//>=0 for(int i=1;i<=n;++i) //每个坑最多注 R-L的水 {ll x=vec[i].second-vec[i].first;ans[i]+=min(diff,x);if(x<diff) diff-=x;else diff=0;if(diff==0) break;}for(int i=1;i<=n;++i) cout<<ans[i]<<" ";return 0;
}
363-d 题给了N个点组成的简单无向图，第i个点的点权为Ai，一共有M条边，2≤N≤2×10^5 , N−1≤M≤2×10^5 第i条边为 ui, vi, bi，表示连接u,v两点的边权为bi，求点1到点i的最小路径的权值——权值是路径上经过的点权和边权的和，使用邻接表存图，由于既有点权又有边权，存点u到点v的路径时，直接存储到点v的边的权重加上v点的权值，使用堆优化版dijkstra算法，用小根堆存储{ dist, node} ——到当前点node的最小路径上的权值dis，st数组存储已经遍历的点，避免一个点的新路径和旧路径同时存在，重复操作导致TLE（眼泪，没发现这个，TLE了两次），每次取出堆顶元素，遍历和堆顶元素相连的点，如果距离更新了就入堆，直到堆为空，输出点1到其他点i的距离。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll INF=2e18;// mlog(n)
int n,m;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;vector<ll> a(n+1,0);for(int i=1;i<=n;++i) cin>>a[i];vector<vector<pii>> g(n+1);// id disfor(int i=0;i<m;++i){ll u,v,b;cin>>u>>v>>b;g[u].push_back({v,b+a[v]});g[v].push_back({u,b+a[u]});}priority_queue<pii,vector<pii>,greater<pii>> heap;vector<ll> dist(n+2,INF);heap.push({a[1],1});// dis iddist[1]=a[1];vector<bool> st(n+2,false);while(heap.size()){pii t=heap.top();heap.pop();ll dis=t.first;ll u=t.second;if(st[u]) continue;st[u]=true;for(auto it:g[u])// id wi {ll v=it.first;ll w=it.second;if(dist[v]==INF||w+dis<dist[v]){dist[v]=dis+w;heap.push({dis+w,v});}}}for(int i=2;i<=n;++i) cout<<dist[i]<<" ";return 0;
}
363-c 题，给了一个长为N的串S，2≤K≤N≤10，求对S的字符进行任意排列得到的串T中不是包含长度为K的回文串的数量，包含长度为K的回文串即以某点 i , 1<=i<=N-K,为起点出发对于1<=j<=k有Ti+j=Ti+k+1-j，使用set容器存储S串全排列得到的串，由于手写代码非常麻烦，我们用数组A储存S串的字符下标0-N-1, 使用next_permutation函数得到下标的不同排列并转换成相应的串出入set容器中，接下来判断set容器中的串是不是包含长度为K的回文串，初始答案为set容器大小直接按题目给的定义来判断就行，如果包含长度为K的回文串，答案数量减1，最后输出答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{int n,k;string s;cin>>n>>k>>s;vector<int> a(n);for(int i=0;i<n;++i) a[i]=i;set<vector<char>> st;do{vector<char> t;for(int i=0;i<n;++i) {t.push_back(s[a[i]]);}st.insert(t);}while(next_permutation(a.begin(),a.end()));ll ans = (ll) st.size();for(auto t: st){bool ok=false;for(int i=0;i<=n-k;++i)//起点 {bool yes=true;// 是含k回文的 串 for(int j=0;j<=k-1;++j) {if(t[i+j]!=t[i+k-1-j])//不满足条件，不是 {yes=false;break;}}if(yes) //是含k回文的 串 {ok=true;break;}} if(ok) ans--;}cout<<ans;return 0;
}
363-d 题，给了一个整数N，1≤N≤10^18，输出第N大的回文数，由于N可能非常大，拒绝暴力，直接找规律构造回文数，当回文数是1位数时，0-9，10个，如果N小于等于10，答案就是N-1，当回文数是两位数时，回文数的形式为XX，x的范围是1-9，当N小于等于19时，答案就是N减去10后输出NN，否则，N减去前面回文数的数量19，当回文数为3位或者更多位数时，它的形式大概为 XYZYX或者XYZZYX，并且这两种形式的回文数的个数是相同的，直接找数N的位数i，预处理10的倍数的数组d10，d10[j]表示 10的j次方， i从3开始遍历，t=(i+1)/2，易知位数为 i 的回文数数量共9d10[t-1]，令 s=9d10[t-1]，如果s<N，N-=s，如果s>=N，则N是i位数，跳出循环，开始构造回文数，令t=(i+1)/2，遍历不同位数p，第1位的数字只能从1-9，遍历不同值，如果当前n-d10[t-p]>0，更新n-=d10[t-p];否则记录第p位上和第第i-p+1位上的值，其他位置就可以从0-9遍历了，最后输出答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ios::sync_with_stdio(false);cin.tie(0);ll d10[19];//预处理 d10[0]=1;for(int i=1;i<19;++i){d10[i]=d10[i-1]*10;}ll cnt=0;ll n;cin>>n;if(n<=10){cout<<n-1;return 0;}else if(n<=19){n-=10;cout<<n<<n;return 0;} n-=19; // 3位数 ll i=3;for(;n>0;++i){ ll t=(i+1)/2;// X Y ZZYX || X Y ZYX 两种形式回文数个数相同 ll s=9*d10[t-1];if(s<n) n-=s;else break;//确定 了几位数 }// 确定i位数 i>=3ll t=(i+1)/2;vector<ll> v(i+2); for(ll p=1;p<=t;++p) //遍历不同数位 ，输出选值 {if(p==1)// 1--9for(int y=1;y<10;++y) // 遍历 值 {if(n-d10[t-p]>0) n-=d10[t-p];else{v[p]=v[i-p+1]=y;break;}} else // 0--9 x==t d10[0]==1for(int y=0;y<10;++y){if(n-d10[t-p]>0) n-=d10[t-p];else{v[p]=v[i-p+1]=y;break;} } }for(ll p=1;p<=i;++p) cout<<v[p];return 0;
}
