本弱鸡还有三题没补~~~~~~
A 同源
题意：有三个整数a，b，c和一个目标值k 我们需要找满足gcd(a,b)=gcd(b,c)=gcd(a,c)=k 并且a,b,c不能等于k，其中a+b+c=n
问：是否存在满足条件的a，b，c，只需要输出一组，没有输出-1 -1 -1
分析：由于数据范围很大1e18，如果暴力枚举前2个数a，b，复杂度是n*n 这个复杂度明显不可以接收，然后我们需要剪枝，由于gcd都要是k，循环变量每次应该递增k，这样能加快一点。 最关键的一个剪枝是：当n%k如果不等于0时，说明还有剩余，那么是一定不可能存在的，直接输出-1 -1 -1.
详细请看代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } ll t; ll n,k; int main() { scanf("%lld",&t); while(t--) { scanf("%lld%lld",&n,&k); //这里n%k不写, 会TLE //case通过率为94.64% if(n%k) { printf("-1 -1 -1\n"); continue; } bool f=false; for(ll i=2ll*k;i<=n-2ll*k;i+=k) { if(f)break; for(ll j=2ll*k;j<=i;j+=k) { ll z=n-i-j; if(z<=k||z<0)continue; if(gcd(i,j)==gcd(j,z)&&gcd(i,z)==k) { printf("%lld %lld %lld\n",i,j,z); f=true; break; } } if(f)break; } if(!f)printf("-1 -1 -1\n"); } return 0; }B：分子
题意：给出有机分子C H O，对应 13，1，17的值。求有机化学式子的值。
分析：没有嵌套的括号，那么我只需要从头往后开始跑，用一个flag来标记当前计算的是括号里的还是在括号外的。 遇到左括号后，标记改变，说明接下来的值要单独算，因为是括号里的。然后我们要看后一个值是不是数字，如果是数字，我们就单独计算。 然后如果碰到右括号，flag标记改变，说明一组括号处理好了，但是也需要往后看看是不是有数字，因为括号外面可以加数字。
AC代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } const int N=1e5+100; char s[N]; stack<char>sk; ll zh(char c) { if(c=='C')return 13; if(c=='H')return 1; if(c=='O')return 17; return 0; } int main() { scanf("%s",s+1); int len=strlen(s+1); ll sum=0; ll ans=0; bool f=false; for(int i=1;i<=len;i++) { char c=s[i]; if(c=='(') { f=true; ans=0; continue; } ll num=1; if(i+1<=len&&isdigit(s[i+1])) { num=0; while(i+1<=len&&isdigit(s[i+1])) { num=num*10+(s[i+1]-'0'); i++; } } if(!f)sum+=num*zh(c); else ans+=num*zh(c); if(c==')') { if(i+1<=len&&isdigit(s[i+1])) { num=0; while(i+1<=len&&isdigit(s[i+1])) { num=num*10+(s[i+1]-'0'); i++; } } sum+=num*ans; ans=0; f=false; } //cout<<sum<<endl; } printf("%lld\n",sum); return 0; }C 爵士
水体，直接做，如果是C++，需要会读一行。
AC代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } int t; int n; string s; int main() { IOS; cin>>t; while(t--) { cin>>n; cin.ignore(); int c=0; for(int i=0;i<n;i++) { getline(cin,s); int pos=s.find("2"); if(pos!=s.npos)c++; } double ans=c*1.0/n*1.0; printf("%.10f\n",ans); } return 0; }E 内存
题意：给出一张对应表，每次查询，给出一个十六进制数，要求把这个十六进制数先转换成二进制，然后取2部分，一个是前31-p个二进制数，一个是后p+1个二进制数，前31-p个二进制数转成十进制去表里映射，映射后再转成二进制，然后和后半部分拼接起来，再次转换成16进制，如果不能映射，就输出interrupt!
AC代码：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String z="00000000000000000000000000000000"; while(sc.hasNext()) { int n=sc.nextInt(); int m=sc.nextInt(); int p=sc.nextInt(); int count=(int)Math.pow(2, m-p); int[]a=new int[count]; for(int i=0;i<count;i++) { a[i]=sc.nextInt(); } int q=sc.nextInt(); while(q-->0) { String st=sc.next(); Long shi=Long.valueOf(st, 16); String e=Long.toBinaryString(shi); //System.out.println(e); e=z.substring(e.length())+e; int first=Integer.valueOf(e.substring(0, e.length()-p), 2); //System.out.println(last); boolean f=false; for(int j=0;j<count;j++) { if(first==a[j]) { f=true; first=j; break; } } String ss=Long.toBinaryString(first)+e.substring(e.length()-p); Long x=Long.valueOf(ss, 2); String sk=Long.toHexString(x); if(f==false) { System.out.println("interrupt!"); } else { System.out.println(cal(sk)); } // String two2=Integer.toBinaryString(last); // System.out.println(two+two2); } } } public static String cal(String s) { s=s.toUpperCase(); while(s.length()<=7) { s="0"+s; } return s; } public static String add(String s,int num) { while(s.length()<num) { s="0"+s; } return s; } }F 游戏
题意：给出奇数个点，偶数条边的树，2者进行博弈。
分析：显然可以发现，先手必胜。
AC代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } int t; int n; int u,v; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n-1;i++) { scanf("%d%d",&u,&v); } printf("Yes\n"); } return 0; }G 选择
题意：给出一个长度为n的数组，必须悬着n/2个数，并且不能相邻选，而且第x个数一定要选，问你拿走的最大值是多少。
分析： 第一眼看题，显然是一道dp题。
1、不考虑题目要求，我们会写一个二维dp，dp（i，j）表示前i个数选j个的最大值
2、由于题目n比较大，二维显然不可以，也可以发现，二维有很多状态都是没用的，比如dp[5][7]…
3、x点必须要选，那么在dp前，我们先给x这点的值，先加一个很大的值，这样的目的就是，在dp状态转移的时候，能把这个点选取。
4、然后我们可以发现，当第i项，i是偶数的时候，我们需要选i/2个数。 ①当不选i这个点的时候，前i-1个数就要选i/2个数了。*可以发现如果前i-1个数要选i/2个数，又不能相邻，正好就是奇数项前缀和（也就是选一个隔一个，选一个隔一个） ② 当选i这个点的时候，第i-1的数就不能选了，所以是dp[i-2]+a[i]
if(i%2==0) { dp[i]=max(sum[i-1],dp[i-2]+a[i]); //这里的sum数组存的是奇数项前缀和 }5、i如果是奇数，dp方程就简单了。不选第i项，就是dp[i-1] 选第i项，就是dp[i-2]+a[i]
if(i%2==1) { dp[i]=max(dp[i-1],dp[i-2]+a[i]); //这里的sum数组存的是奇数项前缀和 }AC代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 using namespace std; typedef long long ll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } const int N=200000+100; ll n,x; ll a[N]; ll sum[N]; ll dp[N]; int main() { scanf("%lld%lld",&n,&x); for(ll i=1;i<=n;i++) { scanf("%lld",&a[i]); } //计算奇数项前缀和 a[x]+=1e14; sum[1]=a[1]; for(ll i=3;i<=n;i+=2) { sum[i]=sum[i-2]+a[i]; } // for(ll i=1;i<=n;i+=2) // { // printf("%lld ",sum[i]); // } // printf("\n"); for(ll i=2;i<=n;i++) { if(i%2==1) { dp[i]=max(dp[i-1],dp[i-2]+a[i]); } else { dp[i]=max(sum[i-1],dp[i-2]+a[i]); } } // for(ll i=1;i<=n;i++) // { // printf("%lld%c",dp[i]," \n"[i==n]); // } dp[n]-=1e14; printf("%lld\n",dp[n]); return 0; }有错请指出，如果有疑问，请私信！
