早上起的早,先把游戏每日肝完了,训练就是一个没有游戏的欲望的状态.
感觉最近越来越有流水账的嫌疑.
刷新概念的一题
很怪,所谓乱搞题.撤销操作的一种思路
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--){
int n,m;
cin>>n>>m;
vector<vector<int>> g(m);
for(int i=0;i<m;i++){
int num;cin>>num;
for(int j=0,x;j<num;j++){
cin>>x;x--;
g[i].push_back(x);
}
}
int M = (m+1)/2;
vector<int> cnt(n,0);
vector<vector<int>> used(n);
vector<int> ans(m);
bool ok = true;
for(int i=0;i<m;i++){
if(g[i].empty()) ok = false;
else cnt[g[i][0]]++,ans[i]=g[i][0],used[g[i][0]].push_back(i);
}
for(int i=0;i<n;i++){
if(cnt[i]>M){
for(auto v : used[i]){
for(auto j : g[v]){
if(cnt[j]<M){
cnt[i]--;
ans[v] = j;
cnt[j]++;
break;
}
}
if(cnt[i]<=M) break;
}
}
}
for(int i=0;i<n;i++){
if(cnt[i]>M) ok = false;
}
if(!ok) cout<<"NO\n";
else {
cout<<"YES\n";
for(auto v : ans) cout<<(v+1)<<" ";
cout<<"\n";
}
}
}
P1955 [NOI2015] 程序自动分析
一个并查集,写了一会拿了90分.后来发现,不等于的操作并没有传递性,惯性思维认为写出了错误的代码
原本代码中如果有a->b 0 a->c 0 ，就会错误认为b->c 1
事实上该关系并没有体现。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
int f[maxn*4];
map<int,int> ID;int cnt = 0;
int id(int x){
if(!ID.count(x)) ID[x] = ++cnt;
return ID[x];
}
int find(int k){
return f[k]==k?k:f[k]=find(f[k]);
}
struct Node{
int x,y,e;
bool operator < (const Node&rhs)const{
return e>rhs.e;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--){
int n;cin>>n;
cnt=0;
ID.clear();
bool ok = true;
for(int i=1;i<=2*n+1;i++) f[i] = i;
vector<Node> vec;
for(int i=1;i<=n;i++) {
int x,y,e;
cin>>x>>y>>e;
x = id(x),y=id(y);
vec.push_back({x,y,e});
}
sort(all(vec));
for(int i=0;i<n;i++){
Node &u = vec[i];
int f1 = find(u.x);int f2 = find(u.y);
if(u.e==1) f[f1]=f2;
else if(f1==f2){
ok = false;break;
}
}
if(ok) cout<<"YES\n";
else cout<<"NO\n";
}
}
P1542 包裹快递
一个很裸的二分,不过要注意一点:long double 的输出格式%Lf
然后不知道为什么要用long double
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-5;
#define all(a) (a).begin(), (a).end()
int x[maxn],y[maxn],s[maxn];
int n;
bool check(long double v){
long double st = 0;
for(int i=1;i<=n;i++){
long double nt = st + s[i]*1.0/v;
if(nt>y[i]) return false;
if(nt<x[i]) nt = x[i];
st = nt;
}
return true;
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>s[i];
}
long double L=0,R=1e7;
long double ans = R;
while(R-L>eps){
long double mid = (R+L)/2;
if(check(mid)) ans = mid,R = mid-eps;
else L = mid+eps;
}
printf("%.2Lf\n",ans);
}
D1. Remove the Substring (easy version)
恼羞成怒O(n^3)过了这件事情.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s,t;
cin>>s>>t;
int n = s.length(),m = t.length();
vector<int> pre(n);
int pt = -1;
for(int i=0;i<n;i++){
if(pt+1<m&&s[i]==t[pt+1]) pt++;
pre[i] = pt;
}
pt = m;int ans = 0;
vector<int> suf(n);
for(int i=n-1;i>=0;i--){
if(pt-1>=0&&s[i]==t[pt-1]) pt--;
suf[i] = pt;
}
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
// if(i==0&&j==n-1) continue;
// int l,r,len = j-i+1;
// if(i==0) {
// if(suf[j+1]==0) ans = max(ans,len);
// }
// else if(j==n-1){
// if(pre[i-1]==m-1) ans = max(ans,len);
// }
// else{
// l = i-1,r = j+1;
// if(suf[r]<=pre[l]) ans = max(ans,len);
// }
// }
string tp;pt =0;
for(int k=0;k<i;k++) tp+=s[k];
for(int k=j+1;k<n;k++) tp+=s[k];
for(int k=0;k<tp.size();k++){
if(pt<m&&tp[k]==t[pt]) pt++;
}
if(pt==m) ans = max(ans,j-i+1);
}
}
// for(int i=0;i<n;i++){
// cout<<i<<": "<<pre[i]<<" ";
// }
// cout<<"\n";
// for(int i=0;i<n;i++){
// cout<<i<<": "<<suf[i]<<" ";
// }
cout<<ans<<"\n";
}
D2. Remove the Substring (hard version)
上一题的D2，考察了cf经典的那种双指针,但是我太笨了,一开始还歪的二分,发现可以贪心求出一个位置
i
i
i最右边且对应下个字符串
t
t
t的位置
j
j
j的最右边,这样是最优的.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,i,j,ans;
string s,t;cin>>s>>t;
n = s.length();m = t.length();
for(j=0;j<m;j++){
while(i<n&&s[i]!=t[j]) i++;
i++;
}
ans = n - i;
i = n - 1;
vector<int> pos(m,-1);
for(j=m-1;j>=0;j--){
while(i>0&&s[i]!=t[j]) i--;
pos[j] = i;
i--;
}
ans = max(ans,i+1);
i = 0;
for(j=1;j<m;j++){
while(s[i]!=t[j-1]) i++;
ans = max(ans,pos[j]-i-1);
i++;
}
cout<<ans<<"\n";
return 0;}
P1337 [JSOI2004] 平衡点 / 吊打XXX
似乎是个模拟退火,印象流一下,只拿了89分
似乎就是用于解决一些很难计算的问题,随机一个答案,然后使得能量函数尽量低的答案方向转移这个样子,以后遇到题目再精进下
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
int n;int x[maxn],y[maxn],w[maxn];
double ansx,ansy,ans;
double en(double xx,double yy){
double res = 0.0;
for(int i=1;i<=n;i++){
res+=sqrt((xx-x[i])*(xx-x[i])+(yy-y[i])*(yy-y[i]))*w[i];
}
return res;
}
double T = 1e5;//搞一个温度,这是答案上界
double cold = 0.996;
void tuihuo(){
double t = T;
while(t>1e-18){
double tpx = ansx + (rand()+rand()-RAND_MAX)*t;
double tpy = ansy + (rand()+rand()-RAND_MAX)*t;
double tpe = en(tpx,tpy);
double d = tpe - ans;
if(d<0.0) ans = tpe,ansx = tpx,ansy = tpy;
else if(exp(-d/t)*RAND_MAX>rand()){
ansx = tpx,ansy=tpy;
}
t*=cold;
}
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
//模拟退火板子题
cin>>n;ansx = 0.0,ansy = 0.0;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>w[i];
ansx+=x[i],ansy+=y[i];
}
ansx/=n,ans/=n;ans = en(ansx,ansy);
for(int i=1;i<=3;i++){
tuihuo();
}
printf("%.3lf %.3lf\n",ansx,ansy);
}