SGU 146
题意:就是给你一个长度为l的圈,然后你跑步,每一段给你时间t和速度v,问你最后离起点多远
收获:就是把浮点数转为整数,然后但是会出现精度误差,比如l最多四位小数,那你就加0.00001这样
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 10000; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int main(){ double l; ll n,t,v,L; scanf("%lf%lld",&l,&n); L = (l + 0.00001) * 10000; ll ans = 0; rep(i,0,n){ scanf("%lld%lld",&t,&v); v*=10000; ans += t * v; ans %= L; } ans = min(ans,L - ans); printf("%.6f",ans/10000.0); return 0; }
SGU 179
题意:给你一个括号序列,然后问你他的下一个字典序的括号序列是什么 (<)
收获:我们考虑正常一个序列的下一个字典序列
比如 1 2 5 4 3
他的下一个字典序序列的构造是这个样的,从后往前找到第一个s[i]<s[i+1]的位置
然后交换s[i]后面序列中,稍稍比s[i]大的数字,在这里就是3,然后交换
变成 1 3 5 4 2,然后把s[i]后面的都变成最小字典序
变成 1 3 2 4 5
那么就勾出答案了,
那么对于括号序列,我们可以设)为1,(为0
按上面的构造方法,然后在维护构造的序列合法就行了,因为它初始化是合法的,那么我们改变后保证后面的位置的)大于(就行了,那么前面必然合法
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e4+6; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; char s[maxn]; int dp[maxn][2] = {0};//0表示位置前面有多少个(,1表示位置前面有多少个) int main(){ scanf("%s",s+1); int len = strlen(s+1); rep(i,1,len+1){ if(s[i]=='(') dp[i][0]=dp[i-1][0]+1; else dp[i][0]=dp[i-1][0]; if(s[i]==')') dp[i][1]=dp[i-1][1]+1; else dp[i][1]=dp[i-1][1]; } bool ok = false; repp(i,1,len,2) { if(s[i]=='('&&s[i+1]==')') continue; ok = true; } if(!ok) return puts("No solution"),0; repd(i,len,2){ if(s[i]==')'&&s[i-1]=='('){ if(dp[len][1]-dp[i][1]>dp[len][0]-dp[i][0]){ swap(s[len],s[i-1]); sort(s+i,s+len+1); return printf("%s",s+1),0; } } } return 0; }
SGU 403
题意:提议比较难理解,就是找一个整数n,使得x*n小于1到n-1的和
收获:无
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int main(){ int x; cin>>x; cout<<2*x+1<<endl; return 0; }