日记.
接下来的一个月的时间内准备一天完成6道题
具有针对性的完成
五道题大致为下: 1. 一道CF 1400~1700
2. 一道背包dp(背包完成后会针对性的进行其他的动态规划)
3. 一道图论(单源,多源最短路, 最小生成树,差分约束,树的重心,求最长路以及最短路,拓扑排序)
4. 一道数论(gcd,lcm,博弈论,各种定理等等)
5. 一道基础优化(st表,树状数组,逆序对,前缀和等等)
6. 一道暴力,枚举(具体从CF上找)
Day 1.( 24-2-29 )
第一天的大多数都是板子题,主要是拿来练练手,中间穿插了两道简单的背包,然后和我新学的裴蜀定理
今天还是2.29号,4年轮一次,据说,今天还是星期四,kfc的疯狂星期四并且还是2.29的要28年轮一次,拉满了
//【模板】最小生成树 https://www.luogu.com.cn/problem/P3366 // #include <bits/stdc++.h> // #define int long long // using namespace std; // const int N=1e6+10,mod=1e9+7; // int p[N],n,res,m,cnt; // int find(int x){ // if(x!=p[x]) p[x]=find(p[x]); // return p[x]; // } // struct node{ // int u,v,w; // bool operator<(const node&W) const{ // return w<W.w; // } // }tr[N]; // signed main() // { // std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // cin>>n>>m; // for(int i=1;i<=n;i++) p[i]=i; // for(int i=1;i<=m;i++){ // int a,b,c; cin>>a>>b>>c; // tr[i]={a,b,c}; // } // sort(tr+1,tr+1+m); // for(int i=1;i<=m;i++){ // int u=tr[i].u,v=tr[i].v,w=tr[i].w; // if(find(u)!=find(v)) // p[find(u)]=find(v),res+=w,cnt++; // } // if(cnt<n-1) cout<<"orz"<<endl; // else cout<<res; // return 0; // } //dijkstra // #include <bits/stdc++.h> // #define int long long // using namespace std; // const int N=1e6+10,mod=1e9+7; // typedef pair<int,int>pii; // int n,m,st,dist[N]; // int e[N],ne[N],h[N],w[N],idx; // bool vis[N]; // void add(int a,int b,int c){ // e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; // } // void dijkstra(){ // priority_queue<pii,vector<pii>,greater<pii>>que; // que.push({0,st}),dist[st]=0; // while(!que.empty()){ // auto now=que.top();que.pop(); // int dis=now.first,id=now.second; // if(vis[id]) continue; vis[id]=true; // for(int i=h[id];~i;i=ne[i]){ // int j=e[i]; // if(dist[j]>dis+w[i]){ // dist[j]=dis+w[i]; // que.push({dist[j],j}); // } // } // } // } // signed main() // { // std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // cin>>n>>m>>st; // memset(h,-1,sizeof h); // for(int i=1;i<=n;i++) dist[i]=2147483647; // for(int i=1;i<=m;i++){ // int a,b,c; cin>>a>>b>>c; // add(a,b,c); // } // dijkstra(); // for(int i=1;i<=n;i++) cout<<dist[i]<<' '; // return 0; // } //spfa // #include <bits/stdc++.h> // #define int long long // using namespace std; // const int N=1e6+10,mod=1e9+7; // int dist[N],n,m,res,st; // int e[N],ne[N],h[N],w[N],idx; // bool vis[N]; // void add(int a,int b,int c){ // e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; // } // void spfa(){ // queue<int>que; // que.push(st),dist[st]=0,vis[st]=true; // while(!que.empty()){ // int now=que.front(); que.pop(); // vis[now]=false; // for(int i=h[now];~i;i=ne[i]){ // int j=e[i]; // if(dist[j]>w[i]+dist[now]){ // dist[j]=dist[now]+w[i]; // if(!vis[j]) que.push(j),vis[j]=true; // } // } // } // } // signed main() // { // std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // cin>>n>>m>>st; // memset(h,-1,sizeof h); // for(int i=1;i<=n;i++) dist[i]=2147483647; // for(int i=1;i<=m;i++){ // int a,b,c; cin>>a>>b>>c; // add(a,b,c); // } // spfa(); // for(int i=1;i<=n;i++) cout<<dist[i]<<' '; // return 0; // } //负环 // #include <bits/stdc++.h> // #define int long long // using namespace std; // const int N=1e6+10,mod=1e9+7; // int n,m,st,dist[N],cnt[N]; // int e[N],ne[N],h[N],idx,w[N]; // bool vis[N]; // void add(int a,int b,int c){ // w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; // } // bool spfa(){ // queue<int>que; // que.push(1),dist[1]=0,vis[1]=true; // while(!que.empty()){ // int now=que.front(); que.pop(); // vis[now]=false; // for(int i=h[now];~i;i=ne[i]){ // int j=e[i]; // if(dist[j]>w[i]+dist[now]){ // dist[j]=w[i]+dist[now]; // cnt[j]=cnt[now]+1; // if(cnt[j]>=n) return true; // if(!vis[j]) vis[j]=true,que.push(j); // } // } // } // return false; // } // void solve(){ // cin>>n>>m; // idx=0; // memset(cnt,0,sizeof cnt); // memset(vis,false,sizeof vis); // memset(h,-1,sizeof h); // memset(dist,0x7f,sizeof dist); // for(int i=1;i<=m;i++){ // int a,b,c; cin>>a>>b>>c; // if(c>=0) add(a,b,c),add(b,a,c); // else add(a,b,c); // } // cout<<(spfa()?"YES":"NO")<<endl; // } // signed main(){ // std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve(); // } //小书童——刷题大军 //https://www.luogu.com.cn/problem/P1926 // #include <bits/stdc++.h> // #define int long long // using namespace std; // const int N=1e6+10,mod=1e9+7; // signed main() // { // int n,m,k,r,num=0,res=0; cin>>n>>m>>k>>r; // vector<int>dp(r+1),hk(n+1),t_(m+1),p(m+1); // for(int i=1;i<=n;i++) cin>>hk[i]; // for(int i=1;i<=m;i++) cin>>t_[i]; // for(int i=1;i<=m;i++) cin>>p[i]; // for(int i=1;i<=m;i++){ // for(int j=r;j>=t_[i];j--) dp[j]=max(dp[j],dp[j-t_[i]]+p[i]); // } // for(int i=1;i<=r;i++){ // if(dp[i]>=k){ // num=r-i; // break; // } // } // sort(hk.begin(),hk.end()); // for(int i=1;i<=n;i++){ // if(num<=0) break; // if(num>=hk[i]) num-=hk[i],res++; // } // cout<<res; // return 0; // } //最大约数和 //https://www.luogu.com.cn/problem/P1734 // #include <bits/stdc++.h> // #define int long long // using namespace std; // const int N=1e6+10,mod=1e9+7; // signed main() // { // std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); // int s; cin>>s; // vector<int>num(s+1),dp(s+1); // for(int i=1;i<=s;i++) // for(int j=1;j<=i;j++) // if(!i%j) num[i]+=j; // for(int i=1;i<=s;i++) // for(int j=s;j>=i;j--) dp[j]=max(dp[j],dp[j-i]+num[i]); // cout<<dp[s]<<endl; // return 0; // } //【模板】裴蜀定理 //https://www.luogu.com.cn/problem/P4549 #include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=1e9+7; signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,res=1; cin>>n; vector<int>a(n+1); cin>>a[1]; for(int i=2;i<=n;i++) cin>>a[i],res=__gcd(a[i],res); cout<<res<<endl; return 0; }