windowsでwgetの代わりは
Windowsでwget使いたい場面があったけど、ソフトインストールするのは癪だったので、プログラムちゃちゃっと書いて見ることにした
pythonでやったらほんとにちゃちゃっと終わった
が、出力については要改良BeautifulSoupすごい。prettify()メソッドが勝手に整形してくれた
import sys import urllib2 from BeautifulSoup import BeautifulSoup as bs4 url = sys.argv[1] html = urllib2.urlopen(url) soup = bs4(html.read()) f = open(url[7:]+'.html', 'w') f.write(str(soup)) f.close()
参考
qiita.com
簡単なgraphの実装
頂点とそれと接続する頂点の情報をもつグラフ表現を書いた
なんとなくprintメソッドが欲しくて書くけど,getメソッドを作ったほうがいいんだろうか
#include <iostream> #include <vector> using namespace std; /* * グラフの表現 */ class graph{ private: struct vertex{ int id; vector <vertex*> edge; }; public: vertex *G; int graph_size; graph(int size){ G = new vertex[size]; graph_size = size; for(int i=0; i<size; i++){ G[i].id = i; } } void append(int target_id, int insert_id){ // if( find(G[target_id].edge->begin(),G[target_id].edge->end(),&G[insert_id])!=G[target_id].edge->end() ){ // G[target_id].edge->push_back(&G[insert_id]); // } for(int i=0; i<G[target_id].edge.size(); i++){ if(G[target_id].edge[i]->id == insert_id) return; } G[target_id].edge.push_back(&G[insert_id]); } void print(){ for(int i=0; i<graph_size; i++){ cout << "vertex: " << G[i].id << endl << "edge: "; for(int j=0; j<G[i].edge.size(); j++){ cout << G[i].edge[j]->id << " "; } if(G[i].edge.size()==0) cout << "nothing."; cout << endl; } } }; int main(void){ int n; cin >> n; graph g(n); for(int i=0; i<n; i++){ int id; cin >> id; int m; cin >> m; for(int j=0; j<m; j++){ int temp; cin >> temp; g.append(id,temp); } } g.print(); return 0; } /* sample input 5 0 4 1 2 3 4 1 0 2 2 3 4 3 0 4 0 */
出力結果
続きを読むunion_findの実装
#include <iostream> #include <cstring> #include <vector> using namespace std; class union_find{ private: int *par; int *rank; int size; public: union_find(int n){ par = new int[n]; rank = new int[n]; size = n; for(int i=0; i<n; i++){ par[i] = i; rank[i] = 0; } } int find(int x){ if(par[x]==x){ return x; }else{ return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x==y) return; if(rank[x] < rank[y]){ par[x]=y; }else{ par[y]=x; if(rank[x] == rank[y]) rank[x]++; } } bool same(int x, int y){ return find(x) == find(y); } void print(){ vector <int> t_unit(size); int count=0; for(int i=0; i<size; i++){ if(t_unit[i]==0){ cout << "group " << count++ << endl; t_unit[i]=1; }else{ continue; } for(int j=i; j<size; j++){ if(same(i,j)){ cout << j << " "; t_unit[j]=1; } } cout << endl; } } }; int main(void){ union_find uf(10); uf.print(); cout << "unite: 0-1" << endl; uf.unite(0,1); uf.print(); cout << "unite: 2-3" << endl; uf.unite(2,3); uf.print(); cout << "unite: 1-2" << endl; uf.unite(1,2); uf.print(); return 0; }
出力結果
続きを読む初めての投稿
test
ナップサック問題を解いた
深さ優先探索を用いたものと、漸化式を利用した2重ループを用いた解法の2つ
#include <iostream> #include <map> #include <queue> #include <algorithm> #include <cstring> using namespace std; typedef pair<int,int> P; int dfs(vector <P> vec, int i, int w, int v, int W){ if(i==vec.size() || w>=W) return 0; return max( dfs(vec,i+1,w+vec[i].first, v+vec[i].second,W)+v,dfs(vec,i+1,w, v,W)); } int main(void){ int n; cin >> n; vector <P> v(n); for(int i=0; i<n; i++){ int a,b; cin >> a >> b; v[i] = P(a,b); } int w; cin >> w; // sort(v.begin(), v.end()); cout << dfs(v,0,0,0,w) << endl; // without dfs only loop // int** dp = new int*[n+1]; // for(int i=0; i<n+1; i++){ // dp[i] = new int[w+1]; // } int dp[5][6]; memset(dp,0,sizeof(dp)); for(int i=0; i<n+1; i++){ for(int j=0; j<w+1; j++){ cout << dp[i][j] << " "; } cout << endl; } for(int i=n-1; i>=0; i--){ for(int j=1; j<w+1;j++){ if(j<v[i].first){ dp[i][j]=dp[i+1][j]; }else{ dp[i][j] = max(dp[i+1][j], dp[i+1][j-v[i].first]+v[i].second); } } } cout << dp[0][5] << endl; for(int i=0; i<n+1; i++){ for(int j=0; j<w+1; j++){ cout << dp[i][j] << " "; } cout << endl; } return 0; } /* sample input 4 2 3 1 2 3 4 2 2 5 ans 7 */ <||