MrLuo

MrLuo
11秒前
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0 , r = nums.size() - 1;

while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] > nums[mid + 1])r = mid;
else l = mid + 1;
}
return l;
}
};


MrLuo
3分钟前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while( p != q)
{
p =( p == NULL) ? headB : p -> next;
q = (q == NULL )? headA : q -> next;
}
return p;
}
};


MrLuo
8分钟前
class MinStack {
public:
/** initialize your data structure here. */stack<int> f , g;
MinStack() {

}

void push(int x) {
if(f.empty() || f.top() >= x)f.push(x);
g.push(x);
}

void pop() {
if(f.top() == g.top())f.pop();
g.pop();
}

int top() {
return g.top();
}

int getMin() {
return f.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/


MrLuo
12分钟前
class Solution {
public:
int findMin(vector<int>& nums) {
int r = nums.size() - 1;
while(r > 0 && nums[0] == nums[r])r--;
if(nums[r] >= nums[0])return nums[0];

int  l = 0;
while( l < r)
{
int mid  = l + r  >> 1;
if(nums[mid] < nums[0])r = mid;
else l = mid + 1;
}
return nums[l];
}
};


MrLuo
17分钟前
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
return nums[r];
}
};


MrLuo
19分钟前
class Solution {
public:
int maxProduct(vector<int>& nums) {
int f =nums[0] ,  g = nums[0];
int res = nums[0];
for(int i = 1 ;i < nums.size() ;i++)
{
int a = nums[i] ,fa = f  * a  , gb = g * a;
f = max(a,max(fa, gb));
g = min(a  , min(fa ,gb)   );
res = max(res  , f);
}
return res;
}
};


MrLuo
41分钟前
class Solution {
public:
string reverseWords(string s) {
int k = 0;
for(int i = 0 ;  i < s.size() ;i++)
{
if(s[i] == ' ')continue;
int j = i , t = k;
while(j < s.size() && s[j] != ' ')s[t++] = s[j++];
reverse(s.begin() + k , s.begin() +  t);
s[t++] = ' ';
i = j , k = t;
}
if(k)k--;
s.erase(s.begin() + k , s.end());
reverse(s.begin() , s.end());
return s;
}
};


MrLuo
10小时前
#include <iostream>
#include <queue>
using namespace std;

#define x first
#define y second

const int N = 1e3 + 10;

typedef pair<int,int> PII;

int n;
char map[N][N];
bool vis[N][N];
int dx[] = {-1, 0 , 1 , 0} ,dy[] = {0 , 1 , 0 , -1};

inline bool check(int a, int b)
{
return a >= 0 && a < n && b >= 0 && b < n;
}

void bfs(int x,int y , int& total , int& bound)
{
queue<PII> q;
q.push({x , y});
vis[x][y] = true;

while(q.size())
{
auto t = q.front();
q.pop();
total ++;

bool _isbound = false;
for(int i = 0 ; i < 4 ; i++)
{
int a = t.x + dx[i] , b = t.y + dy[i];

if(!check(a , b))continue;
if(vis[a][b])continue;
if(map[a][b] == '.')
{
_isbound  =true;
continue;
}
vis[a][b] = true;
q.push({a , b});
}
if(_isbound)bound++;
}

}

int main(){
cin >> n;

for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n;j++)
cin >> map[i][j];

int cnt = 0;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
if(!vis[i][j] && map[i][j] == '#')
{
int bound = 0, total = 0;

bfs(i , j , total , bound);
if(bound == total) cnt++;
}
cout << cnt <<endl;
return 0;
}


MrLuo
12小时前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 9 , M = (1 << N) - 1;
#define lowbit(x) -x & x
int n;
int map[N][N];
int col[N],row[N],cell[4][4];
int low[M + 10],one[M + 10];
int ans = -1,cnt;

int getscore(int a,int b,int t){
return (min(min(a - 0 , 8 - a) , min(b - 0 , 8 - b) ) + 6)* t;
}

void draw(int i ,int j ,int x){

int s = 1;

if(x > 0)map[i][j] = x;
else {
s = -1;
x = -x;
map[i][j] = 0;
}

x--;
col[j] -= (1 << x) * s;
row[i] -= (1 << x) * s;
cell[i / 3][j / 3] -= (1 << x) * s;
}
void init(){
for(int i = 0 ; i < 9 ; i++)col[i] = row[i] = cell[i / 3][i % 3]= M;

for(int i = 0 ; i < 9 ; i++)low[1 << i] = i;

for(int i = 0 ; i < 1 << 9 ; i++)
for(int j = i ; j ;j -= lowbit(j))
one[i]++;
}
int get_one(int i ,int j){
return col[j] & row[i] & cell[i / 3][j / 3];
}
void dfs(int cnt , int score)
{
if(cnt == 0)
{
//cout << "true" <<endl;
ans = max(ans , score);
return ;
}
else
{
int minv = 10;
int x , y;
for(int i = 0 ; i < 9 ; i++)
for(int j = 0 ; j < 9 ;j++)
if(!map[i][j])
{
int t = one[get_one(i , j)];
if(t < minv)
{
minv = t;
x = i , y = j;
}
}

for(int i = get_one(x , y) ; i ; i -= lowbit(i))
{
int t = low[lowbit(i)] + 1;
draw(x , y ,t);
dfs(cnt - 1 , score + getscore(x , y ,t));
draw(x , y , -t);
}

}
}

int main(){
init();
int x = 0;
int score = 0;
for(int i = 0 ;i < 9 ; i++)
for(int j = 0 ; j < 9 ; j++)
{
cin >> x;
if(x)
{
draw(i , j , x);
score += getscore(i , j ,x);
}
else cnt++;
}

dfs(cnt , score);
cout << ans << endl;
return 0;
}


MrLuo
1天前
#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;

int n;
int map[N][N];
bool vis[N],use[N];
int being[N][N];
int depth = 0;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int backbe[20][N][N];
inline int f(){//估价函数 F（）
int res=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(being[i][j]!=1&&!vis[map[i][j]]){
vis[map[i][j]]=1;
res++;
}
return res;
}
bool check(int a,int b){
return a >= 0 && a < n && b >= 0 && b < n;
}
inline void operate(int x,int y,int c){//染色操作
being[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
if(being[nx][ny]==1) continue;
if(map[nx][ny]!=c) being[nx][ny]=2;
else operate(nx,ny,c);
}
}

bool dfs(int cur,int last){
int price = f() ;

if(price == 0)return true;
if(cur + price > depth)return false;

for(int c = 0 ; c <= 5 ;c++)
{
if(c == last || !use[c])continue;
int ff=0,tmp[N][N];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
tmp[i][j]=being[i][j];
bool flag = false;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
if(being[i][j] == 2 && map[i][j] == c)
{
operate(i , j ,c);
flag = true;
}
if(!flag)continue;

if(dfs(cur + 1 , c))return true;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
being[i][j]=tmp[i][j];

}
return false;
}

int main(){

while(cin >> n , n)
{
memset(use,false , sizeof(use));
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j ++)
{
cin >> map[i][j] ;
use[map[i][j]] = true;
}
memset(being,0 ,sizeof(being));
depth = f() ;
if(depth  == 1){cout << 0 << endl; continue;}
operate(0 , 0 , map[0][0]);
depth = 0;
//cout << f() <<endl;
while(!dfs(0 , -1)) depth++;
cout << depth << endl;
}

return 0;
}