去迟了,队友已经开始写了,应该是个水题,贴个队友代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<map> #include<set> #include<vector> #include<algorithm> #include<stack> #include<queue> using namespace std; #define INF 1000000000 #define eps 1e-8 #define pii pair<int,int> #define LL long long int int n; char s[1000000]; int main() { //freopen("in2.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); while(n--) { //memset(s,0,sizeof(s)); scanf("%s",s); int t=strlen(s); if(s[t/2]==s[t/2-1]) { cout<<"Do-it"<<endl; } else { cout<<"Do-it-Not"<<endl; } } //fclose(stdin); //fclose(stdout); return 0; }
简单模拟:检查每个记录是否超过2h,记录时间的时候注意是有大部分时间在夜晚则全部记录为夜行时间(分类讨论下)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; int n, a, b, sunrise, sunset, st, et, cost, nt, s1, s2; int toMinut(int h, int s) { return h*60+s; } int main() { #ifdef LOCAL freopen("B.in", "r", stdin); #endif while(scanf("%d", &n)) { if(n == 0) break; s1 = s2 = 0; bool ok = true; for(int i = 0; i < n; i++) { scanf("%d:%d", &a, &b); sunrise = toMinut(a, b); scanf("%d:%d", &a, &b); sunset = toMinut(a, b); scanf("%d:%d", &a, &b); st = toMinut(a, b); scanf("%d:%d", &a, &b); et = toMinut(a, b); //finish input //check if more than 2 hours cost = et - st; if(cost > 120) ok = false; //check if drive in night if(st < sunrise && et <= sunset) { nt = sunrise - st; if(nt*2 >= cost) s2 += cost; } else if(et > sunset && st >= sunset) { nt = et - sunset; if(nt*2 >= cost) s2 += cost; } else if(st >= sunrise && et <= sunset) s2 += cost; else if(st <= sunrise && et >= sunset) { nt = et-sunset + sunrise- st; if(nt*2 >= cost) s2 += cost; } else s1 += cost; } if(s1+s2 >= 3000 && s2 >= 600 && ok) printf("PASS "); else printf("NON "); } return 0; }
暴力枚举每一种情况,可以想到一种分类方式:两个数'运算',其结果与第三个数’运算‘,其结果与第四个数'运算’;(两个数'运算')‘运算’(两个数'运算') (后者我一开始漏掉了)
这样的话,枚举每一种排列,枚举上述方式,枚举每一个符号,枚举第一类时,A?B, B?A都要算进去
第一类用dfs枚举,第二类用三重循环,见代码
感觉还是比较容易漏情况的...
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<map> #include<set> #include<vector> #include<algorithm> #include<stack> #include<queue> using namespace std; #define INF 1000000000 #define eps 1e-8 #define pii pair<int,int> #define LL long long int int n,a[4]; char s[4]={'+','-','*','/'}; char in[4]; bool ok; bool deal(); void dfs(); int main() { //freopen("out.txt","w",stdout); while(scanf("%d",&n)==1&&n) { bool ans=true; for(int i=1;i<=n;i++) { scanf("%s",in); if(ans==false) continue; a[0]=in[0]-'0'; a[1]=in[1]-'0'; a[2]=in[2]-'0'; a[3]=in[3]-'0'; if(deal()==false)//这四个数弄不出10 { ans=false; } } if(ans==true) printf("TRUE "); else printf("BUSTED "); } //fclose(stdin); //fclose(stdout); return 0; } void dfs(int x, int ans) { // cout << x << " " << ans << endl; if(x == 4 && ans == 10) { ok = true; return; } if(ok || x >= 4) return; int c = ans, d = a[x]; dfs(x+1, c+d); dfs(x+1, c-d); dfs(x+1, d-c); dfs(x+1, c*d); if(d != 0) dfs(x+1, c/d); if(c != 0) dfs(x+1, d/c); } int calc(int x, int y, int t) { switch(t) { case 0: return x+y; case 1: return x-y; case 2: return x*y; case 3: return x/y; default: return -1; } } bool deal()//看目前的四个数能不能弄出10 { ok = false; sort(a, a+4); do { dfs(1, a[0]); for(int i = 0; i < 4; i++) { if(a[1] == 0 && i == 3) continue; int x = calc(a[0], a[1], i); for(int j = 0; j < 4; j++) { if(a[3] == 0 && j == 3) continue; int y = calc(a[2], a[3], j); for(int k = 0; k < 4; k++) { if(y == 0 && k == 3) continue; if(calc(x, y, k) == 10) { ok = true; break; } } } } if(ok) return true; }while(next_permutation(a,a+4)); return false; }
贪心做法 从前往后贪就行了(我一开始以为从后往前,这种方式不好处理(队友代码不贴了...)
扩展欧几里德 题意就是求ax+by=c 其中x+y最小
注意到题中条件a < b < c -> b > 0 && x+y最小等价于x最小(正整数)(x+y = x+(c-ax)/b a/b<1 x变大,x+y变大)
后面就是很经典的问题...求x的最小整数解,但是会超long long...
解决办法1: 高精度
解决办法2: 仔细读题,a, b不超过32位,
求x最小整数解时
t = b/gcd(a,b);
xm = ((x*d/gcd(a,b))%t + t) % t
t不会超过32位int,x*d可能会超long long,那么写成 ( x%t * d/gcd(a,b)%t )%t 便解决了(能挖到这个信息的也是吊啊)
出前两题的速度其实还行,队友卡I题其实很久...(很想让他交给我写呀呀!
C题由于对next_permutation理解不深,卡了(next_permutation 数组需要从小到大排列 大致理解原理就明白了)
J题卡精度了,没有估计数据范围也是傻